JDK 7 HashMap原理解读

用针戳左手中指指头

发布于 2021-01-29 11:09:47

1820

发布于 2021-01-29 11:09:47

存储原理

数组是最基本的数据结构，ArrayList内部就是数组实现的，下标定位位置，然后在数组下标位置存放元素，每添加一个元素，下标就+1，map和list有一点相似，就是内部也有个数组，它通过key存放获取对象，以key计算数组下标。使用hashCode的话，得出的值很大，很容易是数组越界，可以使用取余的方式减小这个，那么余多少呢？比如下标是0-7，那么我们可以余它的数组大小（length），hashCode是随机的，得出的下标也是随机的，这也使得数组下标随机平均。

但还有一个问题，hashCode是随机的，但在取余之后得到的值很可能是相同的，比如第一次你存了kk1: vv1，第二次存放kk2: vv2计算key后得出的位置也是同一个位置，那么在同一下标有两个对象了，那么可以链表去解决这个问题；再来一个，也是计算得到同一个下标，考虑一个问题，是插入头部比较快还是尾部比较快？如果是头插法，只需要修改新节点的next的下一个节点指针就行了，而如果是尾插，那么还需要遍历链表，然后修改尾部的指针，显然，尾插法的效率不是很高，map里就是用的头插法，头插法只有next的元素，这是查找下一个元素使用的，它没有向上查找的方式，它的查找方式也是先计算数组下标，得到下标后，找到对应的链表，然后遍历的：

上面只是对map的一个原理说明，并不严谨。

源码解析

这里从HashMap的源码上去看HashMap这个结构，从源码分析理解。

HashMap里有这些个属性：

	// 默认初始容量 16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
	// 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
	// 默认加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
	// 空数组对象
    static final Entry<?,?>[] EMPTY_TABLE = {};
	// 内部数组，
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
	// map长度
    transient int size;
	// 阈值，是否扩容根据这个判断：threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1) => capacity * loadFactor
    int threshold;
	// 加载因子，扩容计算用到
    final float loadFactor;
	// 修改计数
    transient int modCount;
	// hash种子，计算hash值用到，为了是计算的hashCode更加的散列随机。
	transient int hashSeed = 0;

Entry<K,V>[] 的定义里有这么几个属性，只有next，没有向前查找的对象，所以遍历，只能从头往下遍历。

final K key;
V value;
// 指向下一个对象
Entry<K,V> next;
int hash;

构造行数从put方法开始看：

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
    // key == null 的情况
        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 = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

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

put方法一进来就是这个，初始化内部数组

 if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }

进入inflateTable方法，首先它有一个计算容量的方法roundUpToPowerOf2，然后计算阈值threshold，然后是计算哈希种子。

 private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

跟进：

  private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

上面这一串就需要看：

 Integer.highestOneBit((number - 1) << 1)

 public static int highestOneBit(int i) {
        // HD, Figure 3-1
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
        return i - (i >>> 1);
    }

这个是计算小于等于当前值的二次方数，比如下面给定值为17，其结果是16，给定值是18,19,20都会是16，

i=17 =>             
0000 0000 0000 0000 0000 0000 0001 0001 

(i >>  1) =>        
0000 0000 0000 0000 0000 0000 0000 1000

i |= (i >>  1) =>   
0000 0000 0000 0000 0000 0000 0001 1000
...

i |= (i >> 16) =>  
0000 0000 0000 0000 0000 0000 0001 1111

i - (i >>> 1) =>    
0000 0000 0000 0000 0000 0000 0001 1111		
0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0001 0000

roundUpToPowerOf2注释写着要2的每次方数，那为什么要2的幂次方数呢？

可以看看这篇博客： https://blog.csdn.net/LLF_1241352445/article/details/81321991?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.nonecase

其结论就是：用位运算取余，还有就是计算出的数组下标更加散列平均。

了解了highestOneBit方法后，再看上一层代码，为什么要-1，和左移1位？

 Integer.highestOneBit((number - 1) << 1)

原因是

我们要得到的是一个大于等于在给定值的一个2的幂次方数，highestOneBit得到的是一个小于等于给定值的幂次方数，所以左移1位；假如我们给定值为17，那么要得到的结果应该是32，如果我们不左移，最后得到的值肯定是16
假如给定值是16，要得到结果应该是16，左移1位得到32，所以左移前-1得到15，在左移得到30才能得到16

返回put方法有一段：

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

 private V putForNullKey(V value) {
     // 遍历内部数组的第0个位置的链表，查找是否有key == null的键，如果有就返回旧值
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                // 这个方法不管他，跟hashMap没有关系，这个是给它子类（LinkedHashMap）写的。
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

再回到put方法：

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            // 初始化数组
            inflateTable(threshold);
        }
    // 第一种情况key == null
        if (key == null)
            return putForNullKey(value);
    // 计算hash值
        int hash = hash(key);
    // 这里就是hash & (table.length - 1)
    // 计算数组下标
        int i = indexFor(hash, table.length);
    // 遍历数组下标对应的链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 判断key计算的hash值相同，且key值相同
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 设置新值，获取旧值并返回
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
		// 每次修改+1
        modCount++;
    // 如果没有找的对应的，就新增一个
        addEntry(hash, key, value, i);
        return null;
    }

modCount这个标识是一种快速失败的机制，可以这样理解，多线程下，一个线程在遍历，一个线程在新增或删除，遍历了一般，元素被删除了，在遍历的时候就会出现问题，取值、个数都不对了，所以必须抛一个异常结束这个错误操作。

  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);
    }

就看看数组元素转移的方法，其他比较简单就是赋值

 void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
     // 遍历就数组
        for (Entry<K,V> e : table) {
            // 遍历每一个元素下的链表
            while(null != e) {
                Entry<K,V> next = e.next;
                // 重新计算hash值
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // 计算数组下标
                int i = indexFor(e.hash, newCapacity);
                // 转移到新数组
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

而get方法相对简单些

 public V get(Object key) {
        if (key == null)
            // key == null 的情况
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

 private V getForNullKey() {
        if (size == 0) {
            return null;
        }
     // 遍历数组第一个位置的链表
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            // 找到key == null 的元素并返回
            if (e.key == null)
                return e.value;
        }
        return null;
    }

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
		// 计算位置
        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            // 判断hash值、key相同并返回
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-07-06 ，如有侵权请联系 cloudcommunity@tencent.com 删除

hashmap

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

hashmap

编程算法

登录后参与评论

0 条评论

热度