HashTable源码讲解之put(K key,V value)方法

曾经终败给现在 2022-04-01 07:11 117阅读 0赞

我们知道HashTable在利用key值进行Enry<K,V>位置确定时常常会发生冲突，即通过哈希函数计算出的数组下标该位置上早已存储有数据，此时解决冲突有两种方式，一个是开放地址法，另一个是链地址法。开放地址法即遇到冲突时存放位置按系统的方法（线性探测、二次探测以及再哈希法）在数组上确定一个新的没有保存数据的位置；链地址法是在数组的每个数据项都创建一个子链表用于存储映射到相同位置的Entry<K,V>。在jdk 1.8中HashTable应用的是链地址法，下面主要讲解一下HashTable的put方法。

public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key.hashCode());
            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 = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }

以上是jdk 1.8中HashTable类中的put方法源码，程序通过调用该方法可实现键值对的存储。  
1、当key值为null时  
首先看这一句，

if (key == null)
                return putForNullKey(value);

我们知道HashTable的key与value是可以为null的，这个if语句就是判断当key值为null时调用putForNullKey(value)方法，该方法如下：

private V putForNullKey(V value) {
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(0, null, value, 0);
            return null;
        }

当key为null时默认保存的数组位置是table\[0\]（table即哈希表中用于存储数据的数组）。

for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }

该for循环用于判断table\[0\]是否保存有数据，如果有数据就将原来保存在该位置的Entry<K,V>的value值替换为新的value值，返回旧的value值；如果为空就调用`addEntry(0, null, value, 0);`方法将该Entry<K,V>进行保存，该方法代码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
    	Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
            if (size++ >= threshold)
                resize(2 * table.length);
        }

2、当key值不为null

int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);

首先调用哈希函数计算得出hash值，后一句相当于对 length 取模，也就是 hash%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 = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }

同样首先是判断table\[i\]位置上是否存储有数据，i即刚刚计算出的在数组上的存储位置。如果该位置上保存有数据Entry<K,V>，则`e.hash == hash && ((k = e.key) == key || key.equals(k))`判断原有的Entry的key值是否与新加入的Entry的key值相同，如果相同则进行value值得替换，返回旧的value值

V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;

如果key值首次比较不重复，那么就在该链表上进行第二次、第三次的比较，直到Entry为空，此时跳出循环，将此Entry链接在链表得最后并返回null

modCount++;
     addEntry(hash, key, value, i);
     return null;