[JDK8下的HashMap类应用及源码分析] 数据结构、哈希碰撞、链表变红黑树

系列文章目录

[Java基础] StringBuffer 和 StringBuilder 类应用及源码分析

[Java基础] 数组应用及源码分析

[Java基础] String，分析内存地址，源码

[JDK8环境下的HashMap类应用及源码分析] 第一篇 空构造函数初始化

[JDK8环境下的HashMap类应用及源码分析] 第二篇 看源码了解HashMap的扩容机制

[JDK8环境下的HashMap类应用及源码分析] 第三篇 修改capacity实验

[JDK8环境下的HashMap类应用及源码分析] 第四篇 HashMap哈希碰撞、HashMap存储结构、链表变红黑树

文章目录

• 系列文章目录
• 1、JDK8下的HashMap的数据结构
• • 1.1、hash
  • 1.2、key、value类型
  • 1.3、Node
  • 1.4、TreeNode
  • 1.5、插入数据时的数据结构变化
  • 2、实验
  • • 2.1、哈希碰撞
    • • 2.1.1、与位运算(&)
      • 2.1.2、哈希碰撞
      • 2.2、链表变红黑树

        ---

        1、JDK8下的HashMap的数据结构

        HashMap是一种基于数组和链表（或红黑树）的数据结构，它通过哈希函数将键映射到数组的一个位置，并在该位置存储一个键值对的节点。

        HashMap的put方法在插入数据前，首先要计算键的哈希值（hash(key)）和索引，然后在相应的位置插入或更新节点，如果节点数超过阈值（threshold），就会进行扩容(resize())或树化。

        HashMap的get方法主要是根据键的哈希值和索引，找到对应的位置，然后遍历链表或红黑树，返回匹配的值。

        

        

        1.1、hash

        public class HashMap {
            static final int hash(Object key) {
                int h;
                return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
            }
        }
        public class Object {
            public native int hashCode();
        }
        public final class System {
            /**
             * Returns the same hash code for the given object as
             * would be returned by the default method hashCode(),
             * whether or not the given object's class overrides
             * hashCode().
             * The hash code for the null reference is zero.
             *
             * @param x object for which the hashCode is to be calculated
             * @return  the hashCode
             * @since   JDK1.1
             */
            public static native int identityHashCode(Object x);
        }
        

        下文引用自：深入解析Java对象和类在HotSpot VM内部的具体实现

        对象哈希值

        _mark中有一个hash code字段，表示对象的哈希值。每个Java对象都有自己的哈希值，如果没有重写Object.hashCode()方法，那么虚拟机会为它自动生成一个哈希值。哈希值生成的策略如代码清单3-4所示：

        代码清单3-4 对象hash值生成策略

        static inline intptr_t get_next_hash(Thread * Self, oop obj) {

        intptr_t value = 0; if (hashCode == 0) { // Park-Miller随机数生成器 value =

        os::random(); } else if (hashCode == 1) { // 每次STW时生成stwRandom做随机

        intptr_t addrBits = cast_from_oop

        Java层调用Object.hashCode()或者System.identityHashCode()，最终会调用虚拟机层的runtime/synchronizer的get_next_hash()生成哈希值。

        1.2、key、value类型

        	static final int TREEIFY_THRESHOLD = 8;   //链表转红黑树
        	
        	final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                           boolean evict) {
                Node[] tab; Node p; int n, i;
                //判断table是否初始化
                if ((tab = table) == null || (n = tab.length) == 0)
                    //如果是，调用 resize() 方法，进行初始化并赋值
                    n = (tab = resize()).length;
                //通过hash获取下标，如果数据为null
                if ((p = tab[i = (n - 1) & hash]) == null)
                    // tab[i]下标没有值，创建新的Node并赋值
                    tab[i] = newNode(hash, key, value, null);
                else {
                     //tab[i] 下标的有数据，发生碰撞
                    Node e; K k;
                    //判断tab[i]的hash值和传入的hash值相同，tab[i]的的key值和传入的key值相同
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        //如果是key值相同直接替换即可
                        e = p;
                    else if (p instanceof TreeNode)//判断数据结构为红黑树
                        e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
                    else {//数据结构是链表
                        for (int binCount = 0; ; ++binCount) {
                        
                            //p的下一个节点为null,表示p就是最后一个节点
                            if ((e = p.next) == null) {
                                //创建新的Node节点并插入链表的尾部
                                p.next = newNode(hash, key, value, null);
                                //当元素>=8-1，链表转为树(红黑树)结构
                                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                    treeifyBin(tab, hash);
                                break;
                            }
                            //如果key在链表中已经存在，则退出循环
                            if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                                break;
                            //更新p指向下一个节点，继续遍历
                            p = e;
                        }
                    }
                    //如果key在链表中已经存在，则修改其原先key的value值，并且返回老的value值
                    if (e != null) {
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value;
                        afterNodeAccess(e);//替换旧值时会调用的方法(默认实现为空)
                        return oldValue;
                    }
                }
                ++modCount;//修改次数
                //根据map值判断是否要对map的大小扩容
                if (++size > threshold)
                    resize();
                afterNodeInsertion(evict);//插入成功时会调用的方法(默认实现为空)
                return null;
            }
        

        查看putVal源码，key、vlaue数据类型使用泛型，任意引用类型都可以（Java基础类型不可以，因为基本数据类型不能调用其hashcode()方法和equals()方法,进行比较,所以HashMap集合的key只能为引用数据类型,不能为基本数据类型,可以使用基本数据类型的包装类,例如Integer、Double、Long、Float等）。

        1.3、Node

        见【1.2】代码部分，tab变量的类型Node，实现了Map.Entry接口

        Node里有hash、key、value等属性，也有next下一个节点变量（链表）

        Node实现了toString、hashCode、equals等方法；

        static class Node implements Map.Entry {
            final int hash;
            final K key;
            V value;
            Node next;
            Node(int hash, K key, V value, Node 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);
            }
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
            public final boolean equals(Object o) {
                if (o == this)
                    return true;
                if (o instanceof Map.Entry) {
                    Map.Entry e = (Map.Entry)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }
        interface Entry {
           K getKey();
            
           V getValue();
           V setValue(V value);
           boolean equals(Object o);
           int hashCode();
           public static  kc = null;
                            for (TreeNode p = root;;) {
                                int dir, ph;
                                K pk = p.key;
                                if ((ph = p.hash) > h)
                                    dir = -1;
                                else if (ph 

手机扫描二维码访问