首页 > 代码库 > hash查找和hashmap

hash查找和hashmap

2024-07-19 11:50:16   213人阅读

search by hashing

解决顺序查找一一对比的问题，对存入数据的key取hashcode并存入array，查找数据时以key的hashcode作为索引返回数据。

hash collision

没有一种hash算法可以避免hash冲突，所以在发生冲突时要解决冲突：

1，Open Addressiong

当发生冲突时，把冲突的值存入下一个open的位置。

1.1, linear probing

设index=hash(key)，发生冲突时尝试存入index + 1，如果仍然冲突存入index+2，一次类推知道找到n使得index + n的位置open，如果index + n > size，则从1重新查找。

1.2, double hashing

思路同1.1，不同在于查找open位置是使用hash2算法——index = (index +hash2(key) )% size，如果仍然冲突则继续index = (index +hash2(key) )% size，直到找到open的位置。

一个问题是double hashing可能不会遍历所有的index就回到了开始位置，解决这个问题要保证hash2与size之间是相对素数（不存在公因子）。 

1. hash2(key) = 1 + (key % (SIZE - 2)
2. hash2(key) = max(1, (key / SIZE) % SIZE)

2, Chained hashing

hash表的location位置上存的不再是数据，而是一个linkedList，在发生冲突时把新的数据添加到链表中。

算法效率

1，最坏效率与线性查找一直，即所有的entry的hashcode一样，算法退化为线性查找。

2，平均情况下，需要引入load factor概念——loadfactor=recordCount/size，其中recordCount是当前保持数据的数量，size是hash表的容量。Open Addressing方案中load factor小于等于1，Chained hashing中load factor可以高于1。

Load factor (alpha) Open addressing with linear probing 
(1+1/(1-alpha))/2 		Open addressing with double hashing 
-ln(1-alpha)/alpha 		Chained hashing 
1+alpha/2
0.5 1.50 1.39 1.25
0.6 1.75 1.53 1.30
0.7 2.17 1.72 1.35
0.8 3.00 2.01 1.40
0.9 5.50 2.56 1.45
1.0 N/A N/A 1.50
2.0 N/A N/A 2.00
4.0 N/A N/A 3.00

Java中的hashmap

hashmap使用chained hashing的方式实现，并且根据load factor的大小动态调整hash表的capacity。

put 方法: 

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = http://www.mamicode.com/e.value;> 

 
 
 

 
 
 1，空表则初始化表， 
threshold为hashmap扩张capacity的临界值。 

 

 2，根据hashcode确定在表中的index。 
 

 3，遍历index的值，如果找到key相同的Entry则做更新操作，否则知道添加当前值到链表中。 
 

 addEntry方法： 
 

  
 

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }
 

 
 
 

 
 
 1，如果table已经到达了扩张的临界值，扩张当前size为2*size，并且重算表中所有的Entry。 

 

 2，添加当前值。 
 

 threshold的计算： 
 

  
 

threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
 

 
 
 

 
 
 

 
 
参考： 

 

 https://www.cs.bu.edu/teaching/cs113/spring-2000/hash/ 
hash查找和hashmap


联系
我们