程序猿成长之路番外篇--hashmap介绍

最近在网上看hashmap的相关源码，发现基本的知识有所介绍，但有些地方还是讲的不够透彻，所以我打算再给大家分享一下我的理解。1. 基础知识介绍HashMap大家都知道这是java中常见的数据结构，用途广泛，比如可以用作传参的容器，也可以用于spring中bean的管理。它继承了AbstractMap类，是map的后代，所以我们常常可以用向上造型进行创建实例。如：Map<Type1, Typ

zygswo

3856人浏览 · 2022-01-03 21:53:25

zygswo · 2022-01-03 21:53:25 发布

最近在网上看hashmap的相关源码，发现基本的知识有所介绍，但有些地方还是讲的不够透彻，所以我打算再给大家分享一下我的理解。

1. 基础知识介绍

HashMap大家都知道这是java中常见的数据结构，用途广泛，比如可以用作传参的容器，也可以用于spring中bean的管理。它继承了AbstractMap类，是map的后代，所以我们常常可以用向上造型进行创建实例。
如：

Map<Type1, Type2> map = new HashMap<>();

此外，在括号内还可以传入参数，这个参数代表的含义就是hashmap的initCapacity（初始容量），一般取2的幂次方（为什么取这个值后文会讲到），默认为16。
如：

Map<Type1, Type2> map = new HashMap<>(16);

ps: 这里的容量也可以填其他的数字，如10,14等，但是在初始化时会自动转换成不小于该数字的2的幂次方，这个又是怎么做到的后文也会讲。

之后要想往里面存放数据，只要这样写就还可以了:

map.put(key1,value1);
map.put(key2,value2);

要想取数据则这样写：

map.get(key1);   //value1
map.get(key2);	 //value2

此外，map中的entry元素支持循环遍历，代码如下：

for(Map.Entry<Type1,Type2> entry: map.entrySet()) {
	String key = entry.getKey();
	String value = entry.getValue();
	// 后续操作
	...
}

也可以通过以下方式进行遍历，代码如下

for(Type1 key: map.keySet()) {
	String value = map.get(key);
	// 后续操作
	...
}

map还可以通过迭代器进行遍历，代码如下：

Iterator it = map.entrySet().iterator();
while(it.hasNext()) {
	Map.Entry<Type1,Type2> entry = it.next();
	//对entry进行处理
	String key = entry.getKey();
	String value = entry.getValue();
	...
}

map可以删除元素：

map.remove(key1);

但是切记不能在上述两个循环中使用put或者remove方法进行节点的修改，否则会报java.util.ConcurrentModificationException错，因为在源码中，map中的entry的迭代器中有个expectedModCount 变量，而map中也有个变量叫做modCount，就拿remove方法举例，当调用map中的remove方法时，map中的modCount会进行累加，而迭代器中的expectedModCount没有发生变化，这在EntryIterator迭代器中在实现获取下一个节点的操作时会报错，代码如下：

//1.该函数出现在HashMap的HashIterator这个抽象类中
class HashMap<K.V> extends AbstractMap<K.V> implements Map<K,V>, Cloneable, Serializable {
	...
	transient int modCount;//HashMap结构改变的次数
	...
	abstract class HashIterator {
		Node<K,V> next;
	    Node<K,V> current;
	   	int expectedModCount //迭代器改变的次数
	    int index; 
		...
		final HashMap.Node<K,V> nextNode() {
			HashNode node2 = this.next;
			//关键代码
			if(hashMap.this.modCount != this.expectedModCount) {
				throw new ConcurrentModificationException();
			}
			...
		}
		...
	}
	//2.而在map中则通过内部EntryIterator类实现了这个抽象类
	final class EntryIterator extends HashIterator
		implements Iterator<Map.Entry<K,V>> {
		public final Map.Entry<K,V> next() { return nextNode(); }
	}
	//3.在Map.Entry中创建EntryIterator实例
	final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
		public final int size() { 
			return size;
		}
		public final void clear() { 
			HashMap.this.clear();
		}
		public final Iterator<Map.Entry<K,V>> iterator() {
			return new EntryIterator();
		}
		...
	}
}

但如果使用了迭代器中的remove方法，会自动将迭代器中的expectedModCount与map中的modCount同步更新，就避免了报错。

map还可以替换元素
map.replace(Type1 key, Type2 oldValue, Type2 newValue)

2. 存储原理简介

hashmap的基本结构如图所示
在这里插入图片描述
它最底层的数据结构为链表数组，也就是由链表组成的数组，也就是Node<Type1, Type2>[] table。Node 为实现了Map.Entry接口的类（1.8之前叫Entry，1.8之后叫Node，改名字了），用于存储键值对。它的基本构成代码如下图：

static class Node<K,V> implements Map.Entry<K,V> {
	final int hash; //hash值用于确定下标位置
	final K key;
	final V value;
	final Node<K,V> next; //链表下一个元素
	// 注意这里是package的访问修饰符，也就是说外部无法通过
	//Map.Node的形式获取该元素，而是要通过自带的static函数
	// map.entrySet()来获取
	Node(int hash, K key, V value, Node<K,V> next) {
		this.hash = hash;
		this.key = key;
		this.value = value;
		this.next = next;
	}
	public final K getKey() {
		return key;
	}
	public final V getValue() {
		return value;
	}
	public final String toString() {
		return key + "=" + value;
	}
	public final int hashCode(){
		return Objects.hashCode(key) ^ Objects.hashCode(value);
	}
}

细心的小伙伴一定发现了这里的构造方法是package的，只能在同一个包里面访问，所以外部无法通过Map.Node的形式获取该元素，而是要通过自带的方法map.entrySet()来获取。

那么问题来了，既然知道hashmap的底层为链表数组，那么它是怎么进行数据存储的呢？node中的hash值如何计算，它又有什么用途呢？

饭总得一口一口的吃，问题也要一个一个的解决。先看一下数据存储的过程：现在我们想往里面存放一些数据：{“name”: “zhangsan”,“age”:“16”,“sex”,“男”}, 很明显这是一条个人信息数据，我们也可以将其以键值对形式存放进hashmap中。

步骤一: 调用put(key,value)方法
步骤二: 在put(key,value)方法中我们会计算这个键值对的hash值，计算方式如下：

//JDK1.7
static int hash(Object key){
	int h = hashSeed;
	if (0 != h && k instanceof String) {
		return sun.misc.Hashing.stringHash32((String) k);
	}
	h ^= k.hashCode();
	h ^= (h >>> 20) ^ (h >>> 12);
	return h ^ (h >>> 7) ^ (h >>> 4);
}
//JDK1.8
static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

以JDK1.8为例，这里用了无符号右移的运算（高位补0，低位右移），将高16位和key本身的hash值进行异或运算（不用&或|运算是因为这两个运算概率偏向0或1，分布不够均匀）。这样做的好处就是低位保留了高位的特征, 减低了低位重复的可能，使得hash值尽量分布均匀，减少之后在确定主键位置时发生重复冲突的可能。这里用到的hash函数是散列函数，它可以使得不同长度的输入得到相同长度的结果。但具体hashCode函数怎么实现的可能需要小伙伴的帮助了。

步骤三：根据hash值确定该键值对在hashmap中保存的位置。即index。关于这一点，JDK1.7
中有个函数叫indexFor(int h, int length)，（JDK1.8有所调整但原理一致），下面为源代码

static int indexFor(int h, int length) {
	return h & (length-1);
}

这里我来解释一下，h – 表示hash函数计算后的结果，length表示hashmap数组长度，但为什么要让length减1呢？
在解说这点前我先把前面的坑补了，先说说为何数组的默认长度为2的幂次方（默认为16）:
数组长度为2的幂次方有个特征就是它减一后的值最高位后面的每个位上都为1，它与任何数字进行与运算（&）后获取的hash低几位的数据即为结果。

这样做有什么好处呢？好处就是使用了位运算运算快，并且拿hash的值与每位都为1的二进制数进行与运算（不是或、异或运算），减少了冲突的可能，增加了分布的均匀性。
举个例子做与运算：拿 1101（hash）与 0111（length-1 即8-1）做与运算得0101（5）拿 1111
（hash）与 0111（length-1 即8-1）做与运算得0111（7）但是如果做或运算：拿 1101（hash）与
0111（length-1 即8-1）做或运算得0111（7）拿 1111 （hash）与 0111（length-1 即8-1）
做与运算得0111（7）这样就冲突啦。

总之，hash存储的过程如下： put(key,value) -> hash(key) -> indexFor(hash）-> index

那么问题又来了，这个均匀分布也不可能避免出现重复冲突的可能，在这种情况下hashmap该怎么处理? 答案很简单，那就是它会先以链表的形式存储，如果长度超过8，就会以红黑树的形式存储。

为什么之后要以红黑树形式存储？为何要选择临界值为8？
我们学过数据结构应该知道红黑树的查找长度为O(logn) 而链表则是为O(n/2)
当长度< 8 时 logn 和 n/2 的差值不大并且生成红黑树需要额外的开销因此选择链表形式进行存储，但是当长度大于8时（16,32, 64… 因为hashmap扩容是以2倍为倍率进行扩容的）logn 与 n/2 的差值就会变大，这时候红黑树无疑是更好的。

3. 扩容原理简介

– 2022.1.21 经过半个多月的工作我又回来啦-----------------
hashmap 的扩容其实说复杂不算复杂，说简单吧也不简单。话不多说，直奔主题。hashmap的扩容机制如何实现？
首先让我们来看一段源代码：

	/** 
	 * tableSizeFor 是为了实现hashmap扩容而建立的函数，用于
	 * 对数组进行不小于cap的2的幂次方扩容
	 */
    static final int tableSizeFor(int cap) {
        int n = cap - 1; 
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

好，我们现在来分析一下源码，这里的cap很明显是指要分配的hashmap中数组的长度。但是下面的与运算、无符号右移是什么意思？为何cap要先减一之后再加一（如果不超过最大长度的话）呢？

首先我们设置cap为任意的数字，例如31。（一个比较经典的素数）
那么31 - 1 = 30, 转换成二进制为
00000000 00000000 00000000 00011110 （int 为4Bit 即 32 位）
我们可以看到非0的最高位为第5位（自右往左看）
那么 n >>> 1 有（无符号右移一位，即全体往右移动一位，左边补0）
00000000 00000000 00000000 00001111
这时，我们自右往左看，非0的最高位是在第四位，这时候与之前的二进制数进行或运算那么第四位和第五位必然都是1,。（只要有一个位置上的数字为1那么结果就是1），n |= n >>> 1 的结果如下所示
00000000 00000000 00000000 00011111
之后将上面的结果再次进行无符号右移两位，得
00000000 00000000 00000000 00000111
原先在第四第五位上的1移到了第二第三位，再进行或运算，即 n |= n >>> 2的结果为：
00000000 00000000 00000000 00011111
之后的结果同理可证。
由此可知经过以上代码后，自右往左看，低位部分都为1，高位部分都为0，再加上1 即为2的幂次方。此算法岂不妙哉！

那么这么算的目的是什么呢？这个算法又巧妙在哪里呢?
该算法目的是为了将非2的幂次方的数转化为不小于该数的2的幂次方数
首先就是使用了位运算提高了运算效率，其次是使用或运算和无符号右移的巧妙结合减少了运算量，只需执行5次即可得到结果。牛掰啊！

还有为何cap要先减一之后再加一（如果不超过最大长度的话）呢?
再来举个例子，就拿cap为32来说，如果不先减一的话，
32 转换成二进制为
00000000 00000000 00000000 00100000
之后n |= n >>> 1 有
00000000 00000000 00000000 00110000
再然后n |= n >>> 2：
00000000 00000000 00000000 00111100
以此类推
…
最后 + 1得到的就不是32而是64，即
00000000 00000000 00000000 01000000 ，
那么这个数就不是不小于32的2的幂次方（理应为32）

有了以上基础的知识，那么我们现在可以来讲讲扩容的原理了：
在此再次感谢lkforce大佬的分享，链接如下：
https://blog.csdn.net/lkforce/article/details/89521318
首先看一下源码：

	// jdk1.7
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
         Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
    /**
     * 从原hashmap数组中迁移数据到新数组中.
     */
    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;  //step1  
                if (rehash) { // 重新计算hash值
                    e.hash = null == e.key ? 0 : hash(e.key);
                } 
                int i = indexFor(e.hash, newCapacity);  //step2 
                e.next = newTable[i]; // step3        
                newTable[i] = e;  //断点                     
                e = next;                             
            }
        }
    }

对于jdk1.7来说，扩容主要有以下几步：

分配新的内存空间
复制数据
更新阈值（threshold）一般为装载因子* 新的数组容量

这里我就主要展开讲一下transfer这个函数，它用链表从头到尾进行查询并且它用了头插法进行插入。

首先在step1中，将当前节点的后继节点保存进next中。
在step2中，根据当前的hash值再次获取索引位置。（indexFor函数前面有提到，根据低n位去判断他的位置）
在step3中将当前节点的后继节点设为newTable[i]，方便进行链表重组, 也就是说将当前节点的后继节点指向新数组上newTable上的第i位。
step4就是把newTable[i]的值替换为当前节点，
step5是在原数组继续寻找下一个节点。
这里觉的绕的小伙伴可以去看一下下面的链接。https://blog.csdn.net/lkforce/article/details/89521318

注意：该方法在多线程下使用会存在死链（环形链表）和数据丢失的情况。具体原理详见：
https://blog.csdn.net/XiaoHanZuoFengZhou/article/details/105238992

jdk1.8 扩容:

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;//首次初始化后table为Null
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;//默认构造器的情况下为0
        int newCap, newThr = 0;
        if (oldCap > 0) {//table扩容过
             //当前table容量大于最大值得时候返回当前table
             if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
            //table的容量乘以2，threshold的值也乘以2           
            newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
        //使用带有初始容量的构造器时，table容量为初始化得到的threshold
        newCap = oldThr;
        else {  //默认构造器下进行扩容  
             // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
        //使用带有初始容量的构造器在此处进行扩容
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                HashMap.Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    // help gc
                    oldTab[j] = null;
                    if (e.next == null)
                        // 当前index没有发生hash冲突，直接对2取模，即移位运算hash &（2^n -1）
                        // 扩容都是按照2的幂次方扩容，因此newCap = 2^n
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof HashMap.TreeNode)
                        // 当前index对应的节点为红黑树，这里篇幅比较长且需要了解其数据结构跟算法，因此不进行详解，当树的个数小于等于UNTREEIFY_THRESHOLD则转成链表
                        ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        // 把当前index对应的链表分成两个链表，减少扩容的迁移量
                        HashMap.Node<K,V> loHead = null, loTail = null;
                        HashMap.Node<K,V> hiHead = null, hiTail = null;
                        HashMap.Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                // 扩容后不需要移动的链表
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                // 扩容后需要移动的链表
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            // help gc
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            // help gc
                            hiTail.next = null;
                            // 扩容长度为当前index位置+旧的容量
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

云原生

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

云原生

所有评论(0)

查看更多评论

zygswo

@qq_31236027

已为社区贡献1条内容