一、什么是哈希表

  • 设计精妙、用途广泛的数据结构之一
  • 拥有键值对元素的无序集合
  • 键的值是唯一的,键对应的值可以通过键来获取、更新或移除
  • 无论这个哈希表有多大,这些操作基本上通过常量时间的键比较就可完成

基础操作时间复杂度

  • Insert O(1)
  • Delete O(1)
  • Find O(1)

java hash的基本操作

API
API

HashMap的遍历方式

Iterator<Entry<String,String>> iterator = map.entrySet().iterator();
while(iterator.hasNext()){
    Map.Entry<String,String> entry = (Map.Entry<String,String>) iterator.next();
    System.out.println("Key:" + entry.getKey() + "Value:" + entry.getValue());
}

for(Map.Entry<String,String > entry : map.entrySet()){
    System.out.println("Key:" + entry.getKey() + "Value:" + entry.getValue());
}

for(Object entry : map.entrySet()){
    System.out.println("Key:" + entry.getKey() + "Value:" + entry.getValue());
}

map.entrySet().forEach(entry -> System.out.println("Key:" + entry.getKey() + "Value:" + entry.getValue()); );

二、哈希函数

  • 哈希函数是用来将一个字符串(或任何其他类型)转化为小于哈希表大小且大于等于零的整数
  • 一个好的哈希函数:可以尽可能少地产生冲突,算得快

一种广泛使用的哈希函数算法

hashcode(“abcd”) = (ascii(a) * 33 ^ 3 + ascii(b) * 33 ^2 + ascii© 33 + ascii(d)) % HASH_SIZE= (97 33 ^ 3 + 98 * 33 ^ 2 +99 * 33 +100) % HASH_SIZE= 3595978 % HASH_SIZE

  • 其中HASH_SIZE表示哈希表的大小(可以假设一个哈希表就是一个索引0 ~ HASH_SIZE-1的数组)。
  • 给出一个字符串作为key和一个哈希表的大小,返回这个字符串的哈希值。

对于上述算法用函数来表示

public int hashCode (char[] key, int hashSize){
    long result = 0;
    for(int i = 0; i<key.length;i++){
        result = (result * 33 + (int)key[i]) % hashSize
    }
    return (int) result;
}

然而 冲突 不可避免:

  • 无论使用什么hash function,都需要考虑冲突问题
  • 为啥会有冲突:有一些key会map到相同的index上,无限空间往有限空间映射

hash冲突示意图
hash冲突示意图

如何解决冲突?

  • 没有排满,得到相同的index会冲突
  • 空间 size 小于放入的值的数量也一定会冲突

三、开散列 VS 闭散列

解决方式

  • 步骤1:改变index :Open hashing / Closed hashing
  • 步骤2:扩容装填因子Load factor: size/capacity,Java: LF > 0.75, resize()

Open hashing

把底层的int[] 声明成 LinkList[],每一次存的时候都把key value存到ListNode,如果index重复了就遍历LinkList,找到正确的位置把key,value链接在该链表上。

当链表长度大于8的时候,就会把链表变成树BST(红黑树),这样可以提高查找速度

底层示意图
底层示意图

class ListNode {
    private int key;
    private int value;
    private ListNode next;

    public ListNode(int key, int value){
        this.value = value;
        this.key = key;
    }
}

扩容:重哈希rehashing

哈希表容量的大小在一开始是不确定的。如果哈希表存储的元素太多,我们应该将哈希表容量扩大一倍,并将所有的哈希值重新安排。

重哈希rehashing
重哈希rehashing

public ListNode[] rehashing(ListNode[] hashTable){
    if(hashTable == null || hashTable.length == 0){
        return null;
    }
    int capacity =hashTable.length;
    int newCapacity = capacity*2;
    ListNode[] newHashTable = new ListNode[newCapacity];
    for(ListNode head : hashTable){
        while(head != null){
            int value = head.value;
            int key = head.key;
            int hashcode = (key % newCapacity + newCapacity) % newCapacity;

            if(newHashTable[hashcode] != null){
                ListNode node = newHashTable[hashcode];
                ListNode keyNode = new ListNode(key,value);

                while(node != null && node.next != null){
                    node = node.next;
                }
                node.next = keyNode;
            }
            else{
                newHashTable[hashcode] = new ListNode(key,value)
            }
            head = head.next;
        }
    }
    return newHashTable;
}

Closed hashing

  • 如果index重复了,就找下面空的位置填充,当数组length达到一定的长度的时候就继续扩容,始终保持闭散列方式存在空的位置。