hashMap的内部实现原理(JDK1.8 hashmap改动)

    xiaoxiao2025-01-28  9

    1.hashmap结构

    学过java的或者其他语言的我们都应该对数组和链表不会感到陌生。当然很清楚他们的优点和缺点。 队列:查询方便,插入,删除效率低,因为插入删除一个元素后,后面的元素都要重新下序号。 链表:插入,删除方便,但是查询效率低,链表查询要一个一次一次找下去

    所以hashmap结合了两者的优点。

    可以从上面的图(网上找的),可以看出hashMap是由数组和链表组成(我看的源码为jdk1.7,JDK1.8当链表的长度很大时,会使用红黑树的方式)

    首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

    2.hashmap源码解析

    (有些细节被我忽略了,方便学习,以下源码摘选自JDK1.7)

    2.1构造

    HashMap map=new HashMap<>(); public HashMap() { //当我们不传参数时,默认运行这个构造函数 //DEFAULT_INITIAL_CAPACITY=16,为我们需要的数组长度 //DEFAULT_LOAD_FACTOR=0.75,是hashmap到达现在数组的多少时,进行扩大 //比如现在的数组为16,当hashmap的数组存放到达16*DEFAULT_LOAD_FACTOR时,进行扩大 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } //接下来调用的函数,也是传入参数的方法 //传参数时 public HashMap(int initialCapacity, float loadFactor) { //当长度太长时, if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; this.loadFactor = loadFactor; threshold = initialCapacity; //在hashmap里这个方法做事情,但是他的子类里可以实现自己的方法 //这是模板设计模式的钩子函数~~ init(); }

    我们可以看出其实在hashmap实例化的时候并没有创建数组等等,只是定义了loadFactor ,threshold 两个变量。其实hashmap的数组要在put第一个值时出现。

    2.2 存放变量

    put一个东西 map.put(1,”111”);

    public V put(K key, V value) { //当hashmap的table,也就是hashMap的数组为空时,初始化数组 if (table == EMPTY_TABLE) { //看2.2.1函数 inflateTable(threshold); } if (key == null) return putForNullKey(value); //求出hash值 int hash = hash(key); //其实并不是直接把hash值当作key,要把hash与table的长度进行&位运算 int i = indexFor(hash, table.length); //如果在一模一样的key上有值了,就替换原来的值,并返货原值 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++; //在相应的数组上面放入一个Entry,具体看2.2.2 addEntry(hash, key, value, i); return null; }

    2.2.1初始化数组

    //tosize为目前的数组大小 private void inflateTable(int toSize) { // Find a power of 2 >= toSize //这个是通过源码来找出小与等于tosize的最大的2的次方数 //比如3通过运算为2的一次方,17是16(2的4次方),16是16,15就是2的三次方8 int capacity = roundUpToPowerOf2(toSize); //计算出我们定义的边界值,就是到达threshold 时进行扩大,loadFactor是在2.1中初始化的,默认为0.75 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); //构造数组 table = new Entry[capacity]; initHashSeedAsNeeded(capacity); }

    2.2.2 添加Entry

    void addEntry(int hash, K key, V value, int bucketIndex) { //判断size长度是否超过我们的边界值,如果超过,长度就扩大两倍 if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } //添加新的Entry createEntry(hash, key, value, bucketIndex); } //这个方法其实很简单,就是实例化Entry链表,Entry的链表的next就是我们原来的链表 //其实就会在我们的链表头插入了一个新的链表 void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }

    2.3get取数据

    //这个其实很简单 public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } //先得到hash值 int hash = (key == null) ? 0 : hash(key); //把hash与table.length&运算,在遍历链表 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }

    如果大家看的还是不明白的话,可以自己结合jdk的源码,边调试边看。 看完之后可以尝试写一个简单的hashMap(当然jdk的hashMap不单单这么简单。。)


    2017-6-27 添加

    3 JDK1.8源码解析

    JDK1.8版本对hashmap的部分设计做出了修改 ,其中最大的不同是当链表的长度超过64时,数据结构会从链表转换成树的结构以及hash计算的方法。

    在阅读下面的内容时,最好对JDK1.8 关于hashmap的内容大致进行阅读,基本思路和内容大致和1.7雷同。(分析都在对源码有初步了解的情况下)

    3.1 hash坐标的计算

    static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

    通过计算出hash值后,获取下标的操作和以前一样 ,通过(n-1)&hash获取坐标。 hash的散列值是int类型,有32位组成。当我们计算下标的时候,很有可能只用到了后面的几位,所以可能出现分布不均匀的现象。因此通过>>>16的方法,使前16位与后16位相互影响,使分布更加均匀。 也方便后面resize()中调整链表更加方便。

    3.2 添加数据

    Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //前面的判断和以前大致相同 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判断是否是树型结构 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //创建节点 p.next = newNode(hash, key, value, null); //当现在链表长度大于8时会调整结构 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //如果已经存在 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; p.next = newNode(hash, key, value, null);

    整体上区别不大,主要是有两个地方修改: 1. 创建节点的时候,是插入到链表的最后面,1.7版本是插入到头。 2. 当链表的长度大于8时,会对链表的结构做出变化(调用resize方法,见3.3)。 3. 当节点类型是树形节点的时候,使用不同的方式处理。

    当链表的长度大于8时,会运行下列的函数。 有注释看出,这个方法会替代所有的联型的排列方式,除非数组太小,由代码看出是小于64的时候。

    /** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //长度小于64的的时候,是调用resize()方法。 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); //把队列转换成树形的方式。 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }

    3.3 resize方法

    当链表的长度大于8时,会对链表的结构做出变化。

    调整的基本思路为下图。n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。

    因此,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,把0和1的分成两条链表,为0链表的在原来 下标下面,为1的链表转移到j + oldCap的地方。 这种处理方式好处是不需要重新计算下标的值,并且链表的次序也是和原来的保持一致。

    final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //省略一些基本代码,是调整数组的大小,数组大小扩大两倍 table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //如果是树形结构 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; 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) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

    3.3 树形

    当链表的长度大于等于32的的时候,链表的形式会转变成树的结构,树形的结构更加加快的get的速度。

    关于树形结构,hashMap使用的是红黑树(B树的一种),有兴趣的朋友可以去研究研究。 红黑树参考资料:http://www.cnblogs.com/v-July-v/archive/2010/12/29/1983707.html http://www.cnblogs.com/nullzx/p/6111175.html

    参考文献: java中HashMap详解: http://alex09.iteye.com/blog/539545/ hash冲突:https://www.zhihu.com/question/20733617/answer/111577937

    转载请注明原文地址: https://ju.6miu.com/read-1295851.html
    最新回复(0)