Java数据结构——哈希表

这里写目录标题

前言
1. 哈希表
- 1.1 哈希表的概念
- 1.2 哈希函数
- 1.3 冲突
- - 1.3.1 闭散列
  - 1.3.2 开散列
总结

前言

前面已经介绍了Map和Set中的TreeMap和TreeSet，这里来介绍哈希表，HashSet和HashMap。

1. 哈希表

1.1 哈希表的概念

哈希表（Hash Table）是一种数据结构，它通过将键映射到数组中的位置来实现快速的数据查找、插入和删除操作。哈希表利用哈希函数将键转换为数组的索引，从而在平均情况下实现常数时间复杂度的操作。

1.2 哈希函数

哈希函数是哈希表中最关键的部分，它将输入的键转换为数组中的索引，从而实现快速的数据查找、插入和删除操作。一个好的哈希函数应当尽可能均匀地分布键，以减少冲突。
举例：
当使用数字作为数据集合，并结合哈希函数将这些数字存放在哈希表中时，我们需要选择一个合适的哈希函数来将数字映射到哈希表的位置。一个简单的方法是取数字除以哈希表的大小取余数，将余数作为哈希表的索引。
举例来说，假设我们有以下数字集合：
{10，25，37}
设一个哈希表，大小为10，索引从0到9。可以使用简单的哈希函数
h(x)= x mod10 来将这些数字存放在哈希表中：
对于数字10，计算
10 mod 10 = 0，将10存放在哈希表的索引0处。
同理，将25存放在哈希表的索引5处。将37存放在哈希表的索引7处。
这样就能将数字存放在哈希表中了。

1.3 冲突

在哈希表中，冲突（Collision）是指两个不同的键通过哈希函数映射到相同的数组索引。冲突是不可避免的，因为哈希表的数组长度是有限的，而键的可能值是无限的。处理冲突的方法主要有两种：闭散列（Closed Hashing）和开散列（Open Hashing）。

1.3.1 闭散列

闭散列，也称为开放地址法（Open Addressing），是在发生冲突时，通过寻找数组中的下一个空闲位置来存储键值对。常见的开放地址法有线性探测、二次探测等。
线性探测：
方法：当发生冲突时，按顺序检查数组中的下一个位置，直到找到空闲位置。
优点：实现简单。
缺点：容易产生“堆积”现象，导致查找效率下降。
二次探测:
方法：当发生冲突时，按平方序列检查数组中的下一个位置（例如，1, 4, 9, 16, …），直到找到空闲位置。
优点：减少“堆积”现象。
缺点：实现稍复杂，可能导致查找效率下降。

1.3.2 开散列

开散列（Open Hashing），也称为链地址法（Separate Chaining），是一种处理哈希表冲突的方法。它通过在每个数组索引处维护一个链表（或其他数据结构，如平衡树），将所有映射到同一索引的键值对存储在这个链表中。
哈希表结构：
哈希表由一个数组和多个链表组成。数组中的每个元素都是一个链表的头节点。
哈希函数将键映射到数组中的索引，索引处的链表存储所有映射到该索引的键值对。

开散列的操作：

插入（Insert）：
计算键的哈希值，找到对应的数组索引。
将键值对插入到该索引处的链表中。如果键已经存在，则更新对应的值。
查找（Search）：
计算键的哈希值，找到对应的数组索引。
遍历该索引处的链表，找到匹配的键值对并返回对应的值。如果未找到，则返回 null。
删除（Delete）：
计算键的哈希值，找到对应的数组索引。
遍历该索引处的链表，找到匹配的键值对并将其删除。

开散列也叫哈希桶(Hash Buckets) 下面是用代码实现哈希桶：

public class HashBucket {static class Node {public int key;public int value;public Node next;public Node(int key, int value) {this.key = key;this.value = value;}}public Node[] array = new Node[10];//存放单链表的头结点public int usedSize;//数据个数public static final float LOAD_FACTOR = 0.75f;//负载因子public void put(int key, int value){int index = key % array.length;//遍历index下标的单链表,如果有key相同的元素,则更新value值Node cur = array[index];while (cur != null){if (cur.key == key){cur.value = value;return;}cur = cur.next;}//头插法Node node = new Node(key, value);node.next = array[index];array[index] = node;//尾插法
//        Node node = new Node(key, value);
//        if (array[index] == null){
//            array[index] = node;
//        }else {
//            Node last = array[index];
//            while (last.next != null){
//                last = last.next;
//            }
//            last.next = node;
//        }usedSize++;//判断负载因子是否大于0.75,如果大于则进行二倍扩容if(calcLoadFactor() >= LOAD_FACTOR){resize();}}private void resize(){Node[] newArray = new Node[array.length * 2];for (int i = 0; i < array.length; i++) {Node head = array[i];while(head != null){int newIndex = head.key % newArray.length;//把head插入到newArray中Node cur = head;head = head.next;cur.next = newArray[newIndex];newArray[newIndex] = cur;}}}private float calcLoadFactor(){return usedSize * 1.0f / array.length;}public int get(int key){int index = key % array.length;Node cur = array[index];while (cur != null){if (cur.key == key){return cur.value;}cur = cur.next;}return -1;}
}