精华内容
下载资源
问答
  • HashMap底层实现原理

    2020-06-08 22:27:12
    HashMap实现原理 1.概述 HashMap是基于哈希表的Map接口的非同步实现。元素以键值对的形式存放,并且允许null键和null值,因为key值唯一(不能重复),因此,null键只有一个。另外,hashmap不保证元素存储的顺序,是...

    HashMap实现原理

    1.概述

    HashMap是基于哈希表的Map接口的非同步实现。元素以键值对的形式存放,并且允许null键和null值,因为key值唯一(不能重复),因此,null键只有一个。另外,hashmap不保证元素存储的顺序,是一种无序的,和放入的顺序并不相同(此类不保证映射的顺序,特别是它不保证该顺序恒久不变)。HashMap是线程不安全的。

    2.继承关系

    public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable
    

    其中相关的属性:(JDK1.8)

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  默认的初始容量
    static final float DEFAULT_LOAD_FACTOR = 0.75f; //加载因子
    static final int TREEIFY_THRESHOLD = 8; //链表长度的阈值,当超过8时,会进行树化(不绝对,如下面源码分析)
    static final int UNTREEIFY_THRESHOLD = 6; //当树中只有6个或以下,转化为链表
    transient int size; //HashMap的大小
    int threshold; //判断是否扩容的阈值
    

    Note:HashMap的扩容操作是一项很耗时的任务,所以如果能估算Map的容量,最好给它一个默认初始值,避免进行多次扩容。HashMap的线程是不安全的,多线程环境中推荐是ConcurrentHashMap

    从下图中看出,HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。
    在这里插入图片描述

    3.HashMap的数据存储结构

    3.1 HashMap由数组+链表+红黑树进行数据的存储

    HashMap采用table数组存储Key-Value的,每一个键值对组成了一个Node节点(JDK1.7为Entry实体,因为jdk1.8加入了红黑树,所以改为Node)。Node节点实际上是一个单向的链表结构,它具有Next指针,可以连接下一个Node节点,以此来解决Hash冲突的问题。

    transient Node<K,V>[] table; //默认数组
    
    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    

    从源码,Node就是数组中的元素,每个 Map.Entry 其实就是一个key-value对,它持有一个指向下一个元素的引用,这就构成了链表。

    3.2 HashMap实现存储和读取

    put操作

    put操作所对应的实现流程如下图所示:
    在这里插入图片描述

    具体的源码实现如下:

    //put操作
    public V put(K key, V value) {
         return putVal(hash(key), key, value, false, true);
    }
    
    //计算key对象的hash值
    static final int hash(Object key) { 
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//进行与操作
    }
    
    //具体添加细节
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            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) //(n - 1) & hash 求数组的下标,判断是否有元素。没有
                tab[i] = newNode(hash, key, value, null);  //直接放入
            else { //有元素
                Node<K,V> e; 
                K k;
                //判断存储的节点是否已存在。
                //1.两个对象的hash值不同,一定不是同一个对象
                //2.hash值相同,两个对象也不一定相等
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p; //存储的节点的key的已存在,直接进行替换
                else if (p instanceof TreeNode) //存储的节点的key的不存在,判断是否为树节点(是不是已经转化为红黑树)
                    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);
                            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 存在映射的key,覆盖原值,将原值返回
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold) //hashmap的容量大于阈值
                resize(); //扩容
            afterNodeInsertion(evict);
            return null;
        }
    
    

    由上面的源码可知,,当添加一个Key-Value时,我们通过hash()计算出Key所对应的hash值,然后去调用putVal()真正的执行put操作。

    1. 首先判断数组是否为空,如果是,则进行初始化。
    2. 其次,根据**(n - 1) & hash**求出要添加对象所在的索引位置,判断此索引的内容是否为空,如果是,则直接存储,
    3. 如果不是,则判断索引位置的对象和要存储的对象是否相同,首先判断hash值知否相等,在判断key是否相等。(1.两个对象的hash值不同,一定不是同一个对象。2.hash值相同,两个对象也不一定相等)。如果是同一个对象,则直接进行覆盖,返回原值。
    4. 如果不是,则判断是否为树节点对象,如果是,直接添加
    5. 当既不是相同对象,又不是树节点,直接将其插入到链表的尾部。在进行判断是否需要进行树化。
    6. 最后,判断hashmap的size是否达到阈值,进行扩容resize()处理。

    resize()扩容操作
    当hashmap中的元素越来越多的时候,碰撞的几率也就越来越高(因为数组的长度是固定的),所以为了提高效率,就要对hashmap的数组进行扩容,而在hashmap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。

    那么hashmap什么时候进行扩容呢?当hashmap中的元素个数超过数组大小loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过160.75=12的时候,就把数组的大小扩展为2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能。

    初始化和扩容的具体流程如下:
    在这里插入图片描述

    	final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                //进行数组的扩容,长度为原来的2倍,阈值为原来的2倍
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
             **//进行数组的初始化,容量为默认值16,阈值为16*0.75**
            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) {
                    Node<K,V> e;
                    //判断当前索引j的位置是否存在元素e
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        //判断 e.next是不是有值,简而言之,就是判断当前位置是否是树或者链表
                        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;
        }
    

    treeifyBin操作
    树化的基本操作流程如下:(不涉及左旋和右旋操作,因为不会呀)
    在这里插入图片描述

    final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; Node<K,V> e;
            //当数组的长度小于最大默认数组长度64时,进行扩容
            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);
            }
        }
        
    //链表节点转化为树节点, 本质上treeNode也是双向链表,从下面的继承关系看,treeNode拥有prev和next属性。
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
            return new TreeNode<>(p.hash, p.key, p.value, next);
    }
    
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
            TreeNode<K,V> parent;  // red-black tree links
            TreeNode<K,V> left;
            TreeNode<K,V> right;
            TreeNode<K,V> prev;    // needed to unlink next upon deletion
            boolean red;
    }
    
    static class Entry<K,V> extends HashMap.Node<K,V> {
            Entry<K,V> before, after;
            Entry(int hash, K key, V value, Node<K,V> next) {
                super(hash, key, value, next);
            }
    }
    
    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    }
    
    //树化的真正操作
    final void treeify(Node<K,V>[] tab) {
                TreeNode<K,V> root = null;
                for (TreeNode<K,V> x = this, next; x != null; x = next) {
                    next = (TreeNode<K,V>)x.next;
                    x.left = x.right = null;
                    //将root节点置为黑色(根据红黑树的定义)
                    if (root == null) {
                        x.parent = null;
                        x.red = false;
                        root = x;
                    }
                    else {
                        K k = x.key;
                        int h = x.hash;
                        Class<?> kc = null;
                        //判断插入节点在红黑树的哪边
                        for (TreeNode<K,V> p = root;;) {
                            int dir, ph;
                            K pk = p.key;
                            //小于root节点,放在左边
                            if ((ph = p.hash) > h)
                                dir = -1;
                            //大于root节点,放在右边
                            else if (ph < h)
                                dir = 1;
                            //等于root节点,经过下面的方法尽心过多次判断,确认是否等于
                            else if ((kc == null &&
                                      (kc = comparableClassFor(k)) == null) ||
                                     (dir = compareComparables(kc, k, pk)) == 0)
                                dir = tieBreakOrder(k, pk);
    
                            TreeNode<K,V> xp = p;
                            //根据dir判断放在左边还是右边
                            if ((p = (dir <= 0) ? p.left : p.right) == null) {
                                x.parent = xp;
                               //放在左边(与root相等,也放在左边)
                                if (dir <= 0)
                                    xp.left = x;
                               //放在右边
                                else
                                    xp.right = x;
                                //进行平衡操作(下面过程省略) 
                                root = balanceInsertion(root, x);
                                break;
                            }
                        }
                    }
                }
                //将隐藏的双向链表调整头结点
                moveRootToFront(tab, root);
            }
    
    
    

    get操作

    public V get(Object key) {
          Node<K,V> e;
          return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    //计算key的hash值
    static final int hash(Object key) {
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    //具体实现
     final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; 
            Node<K,V> first, e; 
            int n; 
            K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) { //数组不能为空并且当前索引位置的元素不能为空;如果为空,直接返回null值
                if (first.hash == hash && // always check first node//检查第一个元素,如果是,直接返回
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {//向下寻找
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }
    
    

    由上面的源码可知,,当通过Key获取值时,我们通过hash()计算出Key所对应的hash值,然后去调用getNode()真正的执行get操作。

    containsKey操作

    public boolean containsKey(Object key) {
            return getNode(hash(key), key) != null;
    }
    
    //计算key的hash值
    static final int hash(Object key) {
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    //具体实现
     final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; 
            Node<K,V> first, e; 
            int n; 
            K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) { //数组不能为空并且当前索引位置的元素不能为空;如果为空,直接返回null值
                if (first.hash == hash && // always check first node//检查第一个元素,如果是,直接返回
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {//向下寻找
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }
    

    containsKey方法是先计算hash然后使用hash和table.length取摸得到index值,遍历table[index]元素查找是否包含key相同的值。

    3.2 HashMap的面试相关

    HashMap和Hashtable的区别

    HashMap和Hashtable都实现了Map接口,。主要的区别有:

    1. 对Null key 和Null value的支持:HashMap可以接受为null的键值(key)和值(value),Hashtable不能接受null值,会产生空指针异常。
    2. 线程是否安全: HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的
    3. 效率: 由于Hashtable是线程安全的,所以在单线程环境下比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。
    4. 初始容量大小和每次扩充容量大小的不同:HashMap初始大小为16,扩容为2的幂次方;HashTable初始为11,扩容为2n+1
    5. 底层结构:HashMap会将链表长度大于阈值是转化为红黑树(会先判断当前数组的长度是否小于 64,是则扩容,而不转化),将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。

    HashMap 和 HashSet区别
    HashSet 底层就是基于 HashMap 实现的。(HashSet的对象相当于存储在HashMap的Key上,所以保证了唯一性)
    在这里插入图片描述

    HashSet如何检查重复
    当你把对象加入HashSet时,HashSet会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的hashcode值作比较,如果没有相符的hashcode,HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象,这时会调用equals()方法来检查hashcode相等的对象是否真的相同。如果两者相同,HashSet就不会让加入操作成功。

    hashCode()与equals()的相关规定:
    如果两个对象相等,则hashcode一定也是相同的
    两个对象相等,对两个equals方法返回true
    两个对象有相同的hashcode值,它们也不一定是相等的
    综上,equals方法被覆盖过,则hashCode方法也必须被覆盖
    hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。
    ==与equals的区别:
    ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同
    ==是指对内存地址进行比较 equals()是对字符串的内容进行比较
    ==指引用是否相同 equals()指的是值是否相同
    

    HashMap 的长度为什么是2的幂次方
    为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。Hash 值的范围值-2147483648到2147483647,前后加起来大概40亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。因此,我们首先用hash对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标 hash%tab.length。但是,当数组的长度为2的幂次方时,hash%tab.length等价于hash&(tab.lenngth-1)。(取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作)。并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方

    HashMap 多线程操作导致死循环问题
    当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。

    展开全文
  • HashMap底层实现原理解析

    万次阅读 多人点赞 2020-12-18 10:37:27
    一:HashMap底层实现原理解析 我们常见的有数据结构有三种结构:1、数组结构 2、链表结构 3、哈希表结构 下面我们来看看各自的数据结构的特点: 1、数组结构: 存储区间连续、内存占用严重、空间复杂度大 优点:...

    一:HashMap底层实现原理解析

    我们常见的有数据结构有三种结构:1、数组结构 2、链表结构 3、哈希表结构 下面我们来看看各自的数据结构的特点:
    1、数组结构: 存储区间连续、内存占用严重、空间复杂度大

    • 优点:随机读取和修改效率高,原因是数组是连续的(随机访问性强,查找速度快)
    • 缺点:插入和删除数据效率低,因插入数据,这个位置后面的数据在内存中都要往后移动,且大小固定不易动态扩展。

    2、链表结构:存储区间离散、占用内存宽松、空间复杂度小

    • 优点:插入删除速度快,内存利用率高,没有固定大小,扩展灵活
    • 缺点:不能随机查找,每次都是从第一个开始遍历(查询效率低)

    3、哈希表结构:结合数组结构和链表结构的优点,从而实现了查询和修改效率高,插入和删除效率也高的一种数据结构
    常见的HashMap就是这样的一种数据结构
    在这里插入图片描述

    HashMap中的put()和get()的实现原理

    • 1、map.put(k,v)实现原理
      (1)首先将k,v封装到Node对象当中(节点)。
      (2)然后它的底层会调用K的hashCode()方法得出hash值。
      (3)通过哈希表函数/哈希算法,将hash值转换成数组的下标,下标位置上如果没有任何元素,就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时,就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false,那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true,那么这个节点的value将会被覆盖。
    • 2、map.get(k)实现原理
      (1)先调用k的hashCode()方法得出哈希值,并通过哈希算法转换成数组的下标。
      (2)通过上一步哈希算法转换成数组的下标之后,在通过数组下标快速定位到某个位置上。如果这个位置上什么都没有,则返回null。如果这个位置上有单向链表,那么它就会拿着K和单向链表上的每一个节点的K进行equals,如果所有equals方法都返回false,则get方法返回null。如果其中一个节点的K和参数K进行equals返回true,那么此时该节点的value就是我们要找的value了,get方法最终返回这个要找的value。

    为何随机增删、查询效率都很高的原因是?
    原因: 增删是在链表上完成的,而查询只需扫描部分,则效率高。

    HashMap集合的key,会先后调用两个方法,hashCode and equals方法,这这两个方法都需要重写。

    为什么放在hashMap集合key部分的元素需要重写equals方法?
    因为equals方法默认比较的是两个对象的内存地址

    二:HashMap红黑树原理分析

    相比 jdk1.7 的 HashMap 而言,jdk1.8最重要的就是引入了红黑树的设计,当hash表的单一链表长度超过 8 个的时候,链表结构就会转为红黑树结构。
    为什么要这样设计呢?好处就是避免在最极端的情况下链表变得很长很长,在查询的时候,效率会非常慢。
    在这里插入图片描述

    • 红黑树查询:其访问性能近似于折半查找,时间复杂度 O(logn);
    • 链表查询:这种情况下,需要遍历全部元素才行,时间复杂度 O(n);

    简单的说,红黑树是一种近似平衡的二叉查找树,其主要的优点就是“平衡“,即左右子树高度几乎一致,以此来防止树退化为链表,通过这种方式来保障查找的时间复杂度为 log(n)。
    在这里插入图片描述
    关于红黑树的内容,网上给出的内容非常多,主要有以下几个特性:

    • 1、每个节点要么是红色,要么是黑色,但根节点永远是黑色的;

    • 2、每个红色节点的两个子节点一定都是黑色;

    • 3、红色节点不能连续(也即是,红色节点的孩子和父亲都不能是红色);

    • 4、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点;

    • 5、所有的叶节点都是是黑色的(注意这里说叶子节点其实是上图中的 NIL 节点);

    在树的结构发生改变时(插入或者删除操作),往往会破坏上述条件 3 或条件 4,需要通过调整使得查找树重新满足红黑树的条件。

    展开全文
  • HashMap底层实现原理详解

    万次阅读 多人点赞 2021-02-13 22:41:16
    文章目录前言一、快速入门二、使用步骤1.引入库2.读入数据总结学习内容:学习时间:学习产出:前言一、pandas是什么?二、使用步骤1.引入库2....随着JDK版本的跟新,JDK1.8对HashMap底层实现进行


    一、快速入门

    示例:有一定基础的小伙伴们可以选择性的跳过该步骤

    HashMap是Java程序员使用频率最高的用于映射键值对(key和value)处理的数据类型。随着JDK版本的跟新,JDK1.8对HashMap底层的实现进行了优化,列入引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别,深入探讨HashMap的数据结构实现和功能原理。
    Java为数据结构中的映射定义了一个接口java.uti.Map,此接口主要有四个常用的实现类,分别是HashMap,LinkedHashMap,Hashtable,TreeMap,IdentityHashMap。本篇文章主要讲解HashMap以及底层实现原理。

    1.HashMap的常用方法

    
    //        Hashmap存值:----------------------------------》 .put("key","value"); ----------》无返回值。
    //
    //        Hashmap取值:----------------------------------》 .get("key");-------------------》 返回Value的类型。
    //
    //        Hashmap判断map是否为空:-----------------------》 .isEmpty(); -------------------》返回boolean类型。
    //
    //        Hashmap判断map中是否存在这个key:--------------》.containsKey("key");------------》返回boolean类型。
    //
    //        Hashmap判断map中是否含有value:----------------》.containsValue("value");-------》返回boolean类型。
    //
    //        Hashmap删除这个key值下的value:----------------》.remove("key");-----------------》返回Value的类型。
    //
    //        Hashmap显示所有的value值:---------------------》.values(); --------------------》返回Value的类型。
    //
    //        Hashmap显示map里的值得数量:-------------------》.size(); ----------------------》返回int类型
    //
    //        HashMap显示当前已存的key:---------------------》 .keySet();-------------------》返回Key的类型数组。
    //
    //        Hashmap显示所有的key和value:-----------------》.entrySet());------------------》返回Key=Value类型数组。
    //
    //        Hashmap添加另一个同一类型的map:--------------》.putAll(map); -----------------》(参数为另一个同一类型的map)无返回值。
    //
    //        Hashmap删除这个key和value:------------------》.remove("key", "value");-------》(如果该key值下面对应的是该value值则删除)返回boolean类型。
    //
    //        Hashmap替换这个key对应的value值(JDK8新增):---》.replace("key","value");-------》返回被替换掉的Value值的类型。
    //
    //        克隆Hashmap:-------------------------------》.clone(); ---------------------》返回object类型。
    //
    //        清空Hashmap:-------------------------------》.clear(); ---------------------》无返回值。
    
    

    2.HashMap的几个重要知识点

    1. HashMap是无序且不安全的数据结构。

    2. HashMap 是以key–value对的形式存储的,key值是唯一的(可以为null),一个key只能对应着一个value,但是value是可以重复的。

    3. HashMap 如果再次添加相同的key值,它会覆盖key值所对应的内容,这也是与HashSet不同的一点,Set通过add添加相同的对象,不会再添加到Set中去。

    4. HashMap 提供了get方法,通过key值取对应的value值,但是HashSet只能通过迭代器Iterator来遍历数据,找对象。


    二、JDK7与JDK8的HashMap区别

    既然讲HashMap,那就不得不说一下JDK7与JDK8(及jdk8以后)的HashMap有什么区别:

    1. jdk8中添加了红黑树,当链表长度大于等于8的时候链表会变成红黑树
    2. 链表新节点插入链表的顺序不同(jdk7是插入头结点,jdk8因为要把链表变为红 黑树所以采用插入尾节点)
    3. hash算法简化 ( jdk8 )
    4. resize的逻辑修改(jdk7会出现死循环,jdk8不会)

    三、HashMap的容量与扩容机制

    1.HashMap的默认负载因子

        /**
         * The load factor used when none specified in constructor.
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        /**
         *默认的负载因子是0.75f,也就是75% 负载因子的作用就是计算扩容阈值用,比如说使用
         *无参构造方法创建的HashMap 对象,他初始长度默认是16  阈值 = 当前长度 * 0.75  就
         *能算出阈值,当当前长度大于等于阈值的时候HashMap就会进行自动扩容
         */
    
    

    面试的时候,面试官经常会问道一个问题:为什么HashMap的默认负载因子是0.75,而不是0.5或者是整数1呢?
    答案有两种:

    1. 阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) 根据HashMap的扩容机制,他会保证容量(capacity)的值永远都是2的幂 为了保证负载因子x容量的结果是一个整数,这个值是0.75(4/3)比较合理,因为这个数和任何2的次幂乘积结果都是整数。

    2. 理论上来讲,负载因子越大,导致哈希冲突的概率也就越大,负载因子越小,费的空间也就越大,这是一个无法避免的利弊关系,所以通过一个简单的数学推理,可以测算出这个数值在0.75左右是比较合理的

    2.HashMap的扩容机制

    写数据之后会可能触发扩容,HashMap结构内,我记得有一个记录当前数据量的字段,这个数据量字段到达扩容阈值的话,它就会触发扩容的操作

    阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) 
    当HashMap中table数组(也称为桶)长度 >= 阈值(threshold) 就会自动进行扩容。
    
    扩容的规则是这样的,因为table数组长度必须是2的次方数,扩容其实每次都是按照上一次tableSize位运算得到的就是做一次左移1位运算,
    假设当前tableSize是16的话 16转为二进制再向左移一位就得到了32 即 16 << 1 == 32 即扩容后的容量,也就是说扩容后的容量是当前
    容量的两倍,但记住HashMap的扩容是采用当前容量向左位移一位(newtableSize = tableSize << 1),得到的扩容后容量,而不是当前容量x2
    

    问题又来了,为什么计算扩容后容量要采用位移运算呢,怎么不直接乘以2呢?
    这个问题就比较简单了,因为cpu毕竟它不支持乘法运算,所有的乘法运算它最终都是再指令层面转化为了加法实现的,这样效率很低,如果用位运算的话对cpu来说就非常的简洁高效。

    3.HashMap中散列表数组初始长度

        /**
         * The default initial capacity - MUST be a power of two.
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /**
         * HashMap中散列表数组初始长度为 16 (1 << 4)
         * 创建HashMap的时候可以设置初始化容量和设置负载因子,
         * 但HashMap会自动优化设置的初始化容量参数,确保初始化
         * 容量始终为2的幂
         */
    
    

    老问题又来了,为啥HashMap中初始化大小为什么是16呢?

    首先我们看hashMap的源码可知当新put一个数据时会进行计算位于table数组(也称为桶)中的下标:

    int index =key.hashCode()&(length-1);

    hahmap每次扩容都是以 2的整数次幂进行扩容

    因为是将二进制进行按位于,(16-1) 是 1111,末位是1,这样也能保证计算后的index既可以是奇数也可以是偶数,并且只要传进来的key足够分散,均匀那么按位于的时候获得的index就会减少重复,这样也就减少了hash的碰撞以及hashMap的查询效率。

    那么到了这里你也许会问? 那么就然16可以,是不是只要是2的整数次幂就可以呢?

    答案是肯定的。那为什么不是8,4呢? 因为是8或者4的话很容易导致map扩容影响性能,如果分配的太大的话又会浪费资源,所以就使用16作为初始大小。


    四、HashMap的结构

    JDK7与JDK8及以后的HashMap结构与存储原理有所不同:
    Jdk1.7:数组 + 链表 ( 当数组下标相同,则会在该下标下使用链表)
    Jdk1.8:数组 + 链表 + 红黑树 (预值为8 如果链表长度 >=8则会把链表变成红黑树 )
    Jdk1.7中链表新元素添加到链表的头结点,先加到链表的头节点,再移到数组下标位置
    Jdk1.8中链表新元素添加到链表的尾结点
    (数组通过下标索引查询,所以查询效率非常高,链表只能挨个遍历,效率非常低。jdk1.8及以
    上版本引入了红黑树,当链表的长度大于或等于8的时候则会把链表变成红黑树,以提高查询效率)


    五、HashMap存储原理与存储流程

    1.HashMap存储原理

    1. 获取到传过来的key,调用hash算法获取到hash值

    2. 获取到hash值之后调用indexFor方法,通过获取到的hash值以及数组的长度算
      出数组的下标 (把哈希值和数组容量转换为二进,再在数组容量范围内与哈希值
      进行一次与运算,同为1则1,不然则为0,得出数组的下标值,这样可以保证计算出的数组下标不会大于当前数组容量)

    3. 把传过来的key和value存到该数组下标当中。

    4. 如该数组下标下以及有值了,则使用链表,jdk7是把新增元素添加到头部节点 jdk8则添加到尾部节点。

    2.HashMap存储流程

    前面寻址算法都是一样的,根据key的hashcode经过高低位异或之后的值,再按位与 &(table.lingth - 1),得到一个数组下标,然后根据这个数组下标内的状况,状况不同,然后情况也不同,大概分为了4种状态:

    ( 1.)第一种就是数组下标下内容为空:
    这种情况没什么好说的,为空据直接占有这个slot槽位就好了,然后把当前.put方法传进来的key和value包装成一个node对象,放到这个slot中就好了。

    ( 2.)第二种情况就是数组下标下内容不为空,但它引用的node还没有链化:
    这种情况下先要对比一下这个node对象的key与当前put对象的key是否完全.相等,如果完全相等的情况下,就行进行replace操作,把之前的槽位中node.下的value替换成新的value就可以了,否则的话这个put操作就是一个正儿.八经的hash冲突,这种情况在slot槽位后面追加一个node就可以了,用尾插法 ( 前面讲过,jdk7是把新增元素添加到头部节点,而jdk8则添加到尾部节点)。

    ( 3.)第三种就是该数组下标下内容已经被链化了:
    这种情况和第二种情况处理很相似,首先也是迭代查找node,看看链表上中元素的key,与当前传过来的key是否完全一致,如果完全一致的话还是repleace操作,用put过来的新value替换掉之前node中的value,否则的话就是一致迭代到链表尾节点也没有匹配到完全一致的node,就和之前的一样,把put进来数据包装成node追加到链表的尾部,再检查一下当前链表的长度,有没有达到树化阈值,如果达到了阈值就调用一个树化方法,树化操作都是在这个方法里完成的。

    ( 4.)第四种情况就是冲突很严重的情况下,这个链表已经转化成红黑树了:
    红黑树就比较复杂 要将清楚这个红黑树还得从TreeNode说起 TreeNode继承了Node结构,在Node基础上加了几个字段,分别是指向父节点parent字段,指向左子节点left字段,指向右子节点right字段,还有一个表示颜色的red字段,这就是TreeNode的基本结构,然后红黑树的插入操作,首先找到一个合适的插入点,就是找到插入节点的父节点,然后红黑树它又满足二叉树的所有特性,所以找这个父节点的操作和二叉树排序是完全一致的,然后说一下这个二叉树排序,其实就是二分查找算法映射出来的结构,就是一个倒立的二叉树,然后每个节点都可以有自己的子节点,本且左节点小于但前节点,右节点大于当前节点,然后每次向下查找一层就能那个排除掉一半的数据,查找效率非常的高效,当查找的过程中也是分情况的。

    1. 首先第一种情况就是一直向下探测,直到查询到左子树或者右子树位null,说明整个树中,并没有发现node链表中的key与当前put key一致的TreeNode,那此时探测节点就是插入父节点的所在了,然后就是判断插入节点的hash值和父节点的hash值大小决定插入到父节点的左子树还是右子树。当然插入会打破平衡,还需要一个红黑树的平衡算法保持平衡。

    2. 其次第二种情况就是根节点在向下探测过程中发现TreeNode中key与当前put的key完全一致,然后就也是一次repleace操作,替换value。


    六、jdk8中HashMap为什么要引入红黑树?

    其实主要就是为了解决jdk1.8以前hash冲突所导致的链化严重的问题,因为链表结构的查询效率是非常低的,他不像数组,能通过索引快速找到想要的值,链表只能挨个遍历,当hash冲突非常严重的时候,链表过长的情况下,就会严重影响查询性能,本身散列列表最理想的查询效率为O(1),当时链化后链化特别严重,他就会导致查询退化为O(n)为了解决这个问题所以jdk8中的HashMap添加了红黑树来解决这个问题,当链表长度>=8的时候链表就会变成红黑树,红黑树其实就是一颗特殊的二叉排序树嘛,这个时间复杂…反正就是要比列表强很多


    七、扩容后的新table数组,那老数组中的这个数据怎么迁移呢

    迁移其实就是挨个桶位推进迁移,就是一个桶位一个桶位的处理,主要还是看当前处理桶位的数据状态把,这里也是分了大概四种状态:
    这四种的迁移规则都不太一样

    (1.)第一种就是数组下标下内容为空:
    这种情况下就没什么可说的,不用做什么处理。

    ( 2.)第二种情况就是数组下标下内容不为空,但它引用的node还没有链化:
    当slot它不为空,但它引用的node还没有链化的时候,说明这个槽位它没有发生过hash冲突,直接迁移就好了,根据新表的tableSize计算出他在新表的位置,然后存放进去就好了。

    ( 3.)第三种就是slot内储存了一个链化的node:
    当node中next字段它不为空,说明槽位发生过hash冲突,这个时候需要把当前槽位中保存的这个链表拆分成两个链表,分别是高位链和低位链

    (4.)第四种就是该槽位储存了一个红黑树的根节点TreeNode对象:
    这个就很复杂了,本文章暂时不做过多的介绍(博主还没整明白 =_=! )




    展开全文
  • JDK1.8HashMap底层实现原理

    多人点赞 热门讨论 2021-05-24 18:25:48
    hashmap是我们开发中用的最常见的集合之一,但是我们是否有了解过他的底层呢?这篇文章我将带您了解一下hashmap的底层 ...在学习hashmap底层原理的时候,我们必须要掌握位运算,别问为什么,往下面看自然知晓 ...

    hashmap是我们开发中用的最常见的集合之一,但是我们是否有了解过他的底层呢?这篇文章我将带您了解一下hashmap的底层

    位运算

    在学习hashmap底层原理的时候,我们必须要掌握位运算,别问为什么,往下面看自然知晓

    我们知道,计算机用的是二进制,也就是010101…这样的字符,当我们输入某一个数字的时候,存入计算机里面的也是二进制譬如说

    • 0-》00000000
    • 1-》00000001
    • 2-》00000010
    • 3-》00000011

    &(按位与)

    参加运算的两个二进制数,同时为1,才为1,否则为0。举例 3&5=1。

    在这里插入图片描述

    |(按位或)

    参加运算的两个二进制数,一个为1就为1,否则为0。2 | 4=6

    在这里插入图片描述

    ^(按位异或)

    参加运算的两个二进制数,位不同则为1,位相同则为0。6^7=1

    在这里插入图片描述

    << (左位移运算符)

    将二进制码整体左移指定位数,左移后空出来的位用“0”填充,例如 -5 << 2 = -20

    例如:2<<4
    00000010->00100000=16

    “>>”(右位移运算符)与 >>(无符号右位移运算符)

    例如:16>>4
    00100000->00000010=2

    好了,现在了解了位运算,那么我们来了解一下hashmap

    hashmap的概述

    • HashMap 基于哈希表的 Map 接口实现,是以 key-value 存储形式存在,即主要用来存放键值对。
    • HashMap 的实现不是同步的,这意味着它不是线程安全的。它的 key、value 都可以为 null,此外,HashMap中的映射不是有序的。
    • jdk1.8 之前 HashMap 由 数组 + 链表 组成,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突(两个对象调用的hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用)而存在的(“拉链法”解决冲突)。
    • jdk1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(或者红黑树的边界值,默认为 8 )并且当前数组的长度大于 64时,此时此索引位置上的所有数据改为使用红黑树存储。

    HashMap 特点:

    • 存储无序;
    • 键和值位置都可以是 null,但是键位置只能存在一个 null;
    • 键位置是唯一的,是由底层的数据结构控制的;
    • jdk1.8 前数据结构是链表+数组,jdk1.8 之后是链表+数组+红黑树;
    • 阈值(边界值)> 8 并且桶位数(数组长度)大于 64,才将链表转换为红黑树,变为红黑树的目的是为了高效的查询;

    HashMap存储数据的过程

    测试代码

     public static void main(String[] args) {
            HashMap map=new HashMap();
            map.put("student1","萧炎");
            map.put("student2","林动");
            map.put("student3","牧尘");
            map.put("student4","古尘沙");
            System.out.println(map);
        }
    

    结果

    在这里插入图片描述

    执行流程分析:

    • 首先程序读到HashMap map=new HashMap();的时候,并不会马上创建一个数组,而是在我们第一次使用hashmap自己的put方法的时候,创建一个长度为16的数组,也叫作桶Node[]table ,这个用来存储数据

    • 当我们需要存入一个数据,比方说(key=a,value=3),首先会先调用重写的String的hashcode方法,计算出对应的hash数值,然后根据数组的长度和某种算法,找到这组数据应该对应的桶位数,就是数组的下标,例如0,1,2,3,4,5…然后查看这个桶里面是否有存其他的数据,如果没有,那么就直接把数据存入桶中,我们加入这一次存在‘3’这个位置
      在这里插入图片描述

    • 当我们又再一次的调用put方法,存入(key=b,value=4)的时候,假设这次算出来的又是存在三号位,这个时候,三号位已经有一个数据了,这个时候会判断两个数据的hash值是否相同,如果不相同,那我们这个时候就会在这个桶下生成一个链表,用来存储数据,这个叫做拉链法

    • 如果相同的话则会对两个数据进行一次判断
      数据相同:直接覆盖
      数据不同:从该桶位的链表开始,一直往下比,直到出现不同的时候,便存在不同的地方的下一个位置,如果这个时候链表长度超过了8,那么链表就会转化成红黑树

    • 在不断的添加新数据的时候,如果某一时刻超过了阈值,并且那个时候要存入数据的地方刚好不为空,那么,我们就要扩容了,每次扩容都是在原来的基础上,扩大2倍,原因后面会讲。

    在这里插入图片描述

    jdk1.8 中引入红黑树的进一步原因:

    1. jdk1.8 以前 HashMap 的实现是数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表有n个元素,遍历的时间复杂度就是O(n),完全失去了它的优势。
    2. 针对这种情况,jdk1.8 中引入了红黑树(查找时间复杂度为 O(logn))来优化这个问题。当链表长度很小的时候,即使遍历,速度也非常快,但是当链表长度不断变长,肯定会对查询性能有一定的影响,所以才需要转成树。

    在这里插入图片描述

    HashMap继承体系

    在这里插入图片描述
    从继承体系可以看出:

    • HashMap 实现了Cloneable接口,可以被克隆。
    • HashMap 实现了Serializable接口,属于标记性接口,HashMap 对象可以被序列化和反序列化。
    • HashMap 继承了AbstractMap,父类提供了 Map 实现接口,具有Map的所有功能,以最大限度地减少实现此接口所需的工作。

    存储结构

    在这里插入图片描述
    在Java中,HashMap的实现采用了(数组 + 链表 + 红黑树)的复杂结构,数组的一个元素又称作
    在添加元素时,会根据hash值算出元素在数组中的位置,如果该位置没有元素,则直接把元素放置在此处,如果该位置有元素了,则把元素以链表的形式放置在链表的尾部。
    当一个链表的元素个数达到一定的数量(且数组的长度达到一定的长度)后,则把链表转化为红黑树,从而提高效率。
    数组的查询效率为O(1),链表的查询效率是O(k),红黑树的查询效率是O(log k),k为桶中的元素个数,所以当元素数量非常多的时候,转化为红黑树能极大地提高效率。

    HashMap基本属性与常量

    基本属性,常量一览

    /*
     * 序列化版本号
     */
    private static final long serialVersionUID = 362498820763181265L;
    
    /**
     * HashMap的初始化容量(必须是 2 的 n 次幂)默认的初始容量为16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    /**
     * 最大的容量为2的30次方
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    /**
     * 默认的装载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    /**
     * 树化阈值,当一个桶中的元素个数大于等于8时进行树化
     */
    static final int TREEIFY_THRESHOLD = 8;
    
    /**
     * 树降级为链表的阈值,当一个桶中的元素个数小于等于6时把树转化为链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;
    
    /**
     * 当桶的个数达到64的时候才进行树化
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    /**
     * Node数组,又叫作桶(bucket)
     */
    transient Node<K,V>[] table;
    
    /**
     * 作为entrySet()的缓存
     */
    transient Set<Map.Entry<K,V>> entrySet;
    
    /**
     * 元素的数量
     */
    transient int size;
    
    /**
     * 修改次数,用于在迭代的时候执行快速失败策略
     */
    transient int modCount;
    
    /**
     * 当桶的使用数量达到多少时进行扩容,threshold = capacity * loadFactor
     */
    int threshold;
    
    /**
     * 装载因子
     */
    final float loadFactor;
    
    
    • 容量:容量为数组的长度,亦即桶的个数,默认为16 ,最大为2的30次方,当容量达到64时才可以树化。
    • 装载因子:装载因子用来计算容量达到多少时才进行扩容,默认装载因子为0.75。
    • 树化:树化,当容量达到64且链表的长度达到8时进行树化,当链表的长度小于6时反树化。

    Hashmap属性解释

    DEFAULT_INITIAL_CAPACITY

    集合的初始化容量(必须是 2 的 n 次幂):

    // 默认的初始容量是16	1 << 4 相当于 1*2的4次方
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    

    提问:为什么是2的次幂呢?如果输入值不是 2 的幂比如 10 会怎么样?

     /**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and the default load factor (0.75).
         *
         * @param  initialCapacity the initial capacity.
         * @throws IllegalArgumentException if the initial capacity is negative.
         */
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
    
    • HashMap 构造方法可以指定集合的初始化容量大小,根据上述讲解我们已经知道,当向 HashMap 中添加一个元素的时候,需要根据 keyhash 值,去确定其在数组中的具体位置。HashMap 为了存取高效,减少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现的关键就在把数据存到哪个链表中的算法。
    • 这个算法实际就是取模,hash % length,而计算机中直接求余效率不如位移运算。所以源码中做了优化,使用 hash & (length - 1),而实际上 hash % length 等于 hash & ( length - 1) 的前提是 length 是2 的 n 次幂。(这段话是摘抄传智播客锁哥的,这个解释确实很完美!)

    例如,数组长度为 8 的时候,3 & (8 - 1) = 3,2 & (8 - 1) = 2,桶的位置是(数组索引)3和2,不同位置上,不碰撞。
    再来看一个数组长度(桶位数)不是2的n次幂的情况:

    数组长度为9 hash为3

    00000011 3
    00001000 8
    ————————
    00000000 0

    数组长度为9 hash为5

    00000101 5
    00001000 8
    ————————
    00000000 0

    数组长度为9,hash为6

    00000101 5
    00001000 8
    ————————
    00000000 0

    由此可见,如果不是2的次幂,hash值很容易一模一样,这样会经常产生哈希碰撞,导致性能下降,所以,这里采用的是2的次幂

    为什么要用2的次幂小结:

    • 由上面可以看出,当我们根据key的hash确定其在数组的位置时,如果n为2的幂次方,可以保证数据的均匀插入,如果n不是2的幂次方,可能数组的一些位置永远不会插入数据,浪费数组的空间,加大hash冲突。
    • 另一方面,一般我们可能会想通过%求余来确定位置,这样也可以,只不过性能不如&运算。而且当n是2的幂次方时: hash & (length1) == hash % length
    • 因此,HashMap容量为2次幂的原因,就是为了数据的的均匀分布,减少hash冲突,毕竟hash冲突越大,代表数组中一个链的长度越大,这样的话会降低hashmap的性能

    如果创建HashMap对象时,输入的数组长度length是10,而不是2的n次幂会怎么样呢?

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

    这里HashMap会采用一个tableSizeFor()方法,通过这个方法,把数组长度设置成最接近自己输入数组长度数量的2的次幂的数量例如如果我输入10,最后返回的就是16,我输入5,那么返回的便是8,我们复制一下这个方法,自己测试 一下

    public class Test01 {
        public static void main(String[] args) {
            System.out.println(tableSizeFor(12));
        }
    
        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 + 1;
        }
    }
    
    

    int n = cap - 1;为什么要减去1呢?

    防止 cap 已经是 2 的幂。如果 cap 已经是 2 的幂,又没有这个减 1 操作,则执行完后面的几条无符号操作之后,返回的 capacity 将是这个 cap 的 2 倍(后面还会再举个例子讲这个)。

    最后为什么有个 n + 1 的操作呢?

    如果 n 这时为 0 了(经过了cap - 1后),则经过后面的几次无符号右移依然是 0,返回0是肯定不行的,所以最后返回n+1最终得到的 capacity 是1。
    注意:容量最大也就是 32bit 的正数,因此最后 n |= n >>> 16;最多也就 32 个 1(但是这已经是负数了,在执行 tableSizeFor 之前,对 initialCapacity 做了判断,如果大于MAXIMUM_CAPACITY(2 ^ 30),则取 MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY,会执行位移操作。所以这里面的位移操作之后,最大 30 个 1,不会大于等于 MAXIMUM_CAPACITY。30 个 1,加 1 后得 2 ^ 30)。

    完整例子

    在这里插入图片描述

    DEFAULT_LOAD_FACTOR

    负载因子:默认为0.75

    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    

    MAXIMUM_CAPACITY

    static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次幂
    
    

    集合最大容量:为2的30次方

    TREEIFY_THRESHOLD

    当桶(bucket)上的结点数大于这个值时会转为红黑树

    // 当桶(bucket)上的结点数大于这个值时会转为红黑树
    static final int TREEIFY_THRESHOLD = 8;
    
    

    为什么 Map 桶中结点个数超过 8 才转为红黑树?

    8这个阈值定义在HashMap中,针对这个成员变量,在源码的注释中只说明了 8 是 bin( bucket 桶)从链表转成树的阈值,但是并没有说明为什么是 8。

    在 HashMap 中有一段注释说明:

    Because TreeNodes are about twice the size of regular nodes, we use them only when bins
    contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too
    small (due to removal or resizing) they are converted back to plain bins.  In usages with
    well-distributed user hashCodes, tree bins are rarely used.  Ideally, under random hashCodes, 
    the frequency of nodes in bins follows a Poisson distribution 
    (http://en.wikipedia.org/wiki/Poisson_distribution) 
    with a parameter of about 0.5 on average for the default resizing
    threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, 
    the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:
    
    翻译:因为树结点的大小大约是普通结点的两倍,所以我们只在箱子包含足够的结点时才使用树结点(参见TREEIFY_THRESHOLD)。
    当它们变得太小(由于删除或调整大小)时,就会被转换回普通的桶。在使用分布良好的用户 hashCode 时,很少使用树箱。
    理想情况下,在随机哈希码下,箱子中结点的频率服从泊松分布。
    默认调整阈值为0.75,平均参数约为0.5,尽管由于调整粒度的差异很大。忽略方差,列表大小k的预朗出现次数是(exp(-0.5)*pow(0.5, k) / factorial(k)
    第一个值是:
    
    0:    0.60653066
    1:    0.30326533
    2:    0.07581633
    3:    0.01263606
    4:    0.00157952
    5:    0.00015795
    6:    0.00001316
    7:    0.00000094
    8:    0.00000006
    more: less than 1 in ten million
    
    

    一句话概括:
    hashCode 算法下所有 桶 中结点的分布频率会遵循泊松分布,这时一个桶中链表长度超过 8 个元素的槪率非常小,权衡空间和时间复杂度,所以选择 8 这个数宇。

    UNTREEIFY_THRESHOLD

    当链表长度低于6会从红黑树转化成链表

    // 当桶(bucket)上的结点数小于这个值,树转为链表 
    static final int UNTREEIFY_THRESHOLD = 6;
    
    

    MIN_TREEIFY_CAPACITY

    当 Map 里面的数量超过这个值时,表中的桶才能进行树形化,否则桶内元素太多时会扩容,而不是树形化为了避免进行扩容、树形化选择的冲突,这个值不能小于4*TREEIFY_THRESHOLD(8)

    // 桶中结构转化为红黑树对应的数组长度最小的值 
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    

    table(重点)

    table 用来初始化(必须是二的n次幂)

    // 存储元素的数组 
    transient Node<K,V>[] table;
    
    

    在 jdk1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构,其中 table 就是 HashMap 中的数组,jdk8 之前数组类型是 Entry<K,V> 类型。从 jdk1.8 之后是 Node<K,V> 类型。只是换了个名字,都实现了一样的接口:Map.Entry<K,V>。负责存储键值对数据的。

    entrySet

    用来放缓存

    // 存放具体元素的集合
    transient Set<Map.Entry<K,V>> entrySet;
    
    

    size(重点)

    HashMap 中存放元素的个数

    // 存放元素的个数,注意这个不等于数组的长度
     transient int size;
    
    

    size 为 HashMap 中 K-V 的实时数量,不是数组 table 的长度。

    modCount

    用来记录 HashMap 的修改次数

    // 每次扩容和更改 map 结构的计数器
     transient int modCount;  
    
    

    threshold(重点)

    用来调整大小下一个容量的值计算方式为(容量*负载因子)

    // 临界值 当实际大小(容量*负载因子)超过临界值时,会进行扩容
    int threshold;
    
    

    loadFactor(重点)

    哈希表的负载因子

    // 负载因子
    final float loadFactor;// 0.75f
    
    

    说明:

    • oadFactor 是用来衡量 HashMap 满的程度,表示HashMap的疏密程度,影响 hash 操作到同一个数组位置的概率,计算HashMap 的实时负载因子的方法为:size/capacity,而不是占用桶的数量去除以 capacity。capacity是桶的数量,也就是 table 的长度 length。
    • loadFactor 太大导致查找元素效率低,太小导致数组的利用率低,存放的数据会很分散。loadFactor 的默认值为 0.75f是官方给出的一个比较好的临界值。
    • 当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时,表示 HashMap
      太挤了,需要扩容,而扩容这个过程涉及到 rehash、复制数据等操作,非常消耗性能。所以开发中尽量减少扩容的次数,可以通过创建HashMap 集合对象时指定初始容量来尽量避免。
    • 在 HashMap 的构造器中可以定制 loadFactor。
    // 构造方法,构造一个带指定初始容量和负载因子的空HashMap
    HashMap(int initialCapacity, float loadFactor);
    
    

    为什么负载因子loadFactor 设置为0.75,初始化临界值threshold是12?

    loadFactor 越趋近于1,那么 数组中存放的数据(entry)也就越多,也就越密,也就是会让链表的长度增加,loadFactor 越小,也就是趋近于0,数组中存放的数据(entry)也就越少,也就越稀疏。
    在这里插入图片描述
    如果希望链表尽可能少些,要提前扩容。有的数组空间有可能一直没有存储数据,负载因子尽可能小一些。

    例举:

    例如:负载因子是0.4。 那么16*0.4--->6 如果数组中满6个空间就扩容会造成数组利用率太低了。
    	 负载因子是0.9。 那么16*0.9--->14 那么这样就会导致链表有点多了,导致查找元素效率低。
    
    

    所以既兼顾数组利用率又考虑链表不要太多,经过大量测试 0.75 是最佳方案。

    threshold 计算公式:capacity(数组长度默认16) * loadFactor(负载因子默认0.75)==12。

    这个值是当前已占用数组长度的最大值。当 Size >= threshold(12) 的时候,那么就要考虑对数组的 resize(扩容),也就是说,这个的意思就是 衡量数组是否需要扩增的一个标准。 扩容后的 HashMap 容量是之前容量的两倍。

    HashMap扩容机制

     /**
         * Initializes or doubles table size.  If null, allocates in
         * accord with initial capacity target held in field threshold.
         * Otherwise, because we are using power-of-two expansion, the
         * elements from each bin must either stay at same index, or move
         * with a power of two offset in the new table.
         *
         * @return the table
         */
        final Node<K,V>[] resize() {
            //把旧的table 赋值个一个变量
            Node<K,V>[] oldTab = table;
            //获取旧的tabel的长度
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 旧的阈值
            int oldThr = threshold;
            int newCap, newThr = 0;
        
            if (oldCap > 0) {
                //判断数组的长度是否大约等于最大值
                if (oldCap >= MAXIMUM_CAPACITY) {
                    //如果数组的长度达到了最大值,那么就不在进行扩容,直接返回,不管了任由hash冲突
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                //把旧的数组长度左移一位(也就是乘以2),然后判断是否小于最大值,并且判断旧的数组长度是否大于等于默认的长度16
                }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    //如果条件成立就把旧的阈值左移一位复制给新的阈值
                    newThr = oldThr << 1; // double threshold
            }//如果就的数组长度小于0并且旧的阈值大于0
            else if (oldThr > 0) // initial capacity was placed in threshold
                //就把旧的阈值赋值给新的数组长度(初始化新的数组长度)
                newCap = oldThr;
            else {               // zero initial threshold signifies using defaults
                //使用默认值 
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            //如果新的阈值等于0
            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) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        //如果没有子元素那么说明是下面不是一个链表,直接通过 hash&(新的数组长度-1)计算出新的位置,把就的数据放入新的位置
                        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
                            //有多个数据并且不是树那么该节点上放的是链表
                            //这里是java1.8很精妙的地方,如果 e.hash& 旧的数组长度 如果等于0
                            那么该数据的位置没有发生变化,还在原来的索引位置上,如果不等于0 那么就在该值就在 (原来的索引位置+旧的数组长度)的位置上,
                            这里重新创建了两个节点,在原来位置上的放入loHead中,在新的位置上的放入
    hiHead 中,最后把这两组数据放入新的数组中即可。(这里的精妙之处是不用重新计算每一个数据的hash,就可以把旧的数据放入新的数组中去)
                            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;
        }
    

    在这里插入图片描述

    内部类

    Node内部类

    Node是一个典型的单链表节点,其中,hash用来存储key计算得来的hash值。

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;// hash用来存储key计算得来的hash值
        final K key;// 键
        V value;// 值
        Node<K,V> next;// 下一个node节点
        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() {// 调用底层c++ 返回Key/Value的哈希码值,如果此对象为null,则返回0
            return Objects.hashCode(key) ^ Objects.hashCode(value);// 将Key/Vaule
        }
        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;
        }
    }
    
    

    HashMap构造方法

    HashMap()

    构造一个空的HashMap,默认初始容量(16)和默认负载因子(0.75)。

    public HashMap() {
       // 将默认的负载因子0.75赋值给loadFactor,并没有创建数组
       this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }
    
    

    HashMap(int initialCapacity)

    构造一个具有指定的初始容量和默认负载因子(0.75)HashMap 。

    // 指定“容量大小”的构造函数
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    

    HashMap(int initialCapacity,float loadFactor)构造方法

    构造一个具有指定的初始容量和负载因子的 HashMap。

    /*
    	 指定“容量大小”和“负载因子”的构造函数
    	 initialCapacity:指定的容量
    	 loadFactor:指定的负载因子
    */
    public HashMap(int initialCapacity, float loadFactor) {
        	// 判断初始化容量initialCapacity是否小于0
            if (initialCapacity < 0)
                // 如果小于0,则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        	// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
            if (initialCapacity > MAXIMUM_CAPACITY)
                // 如果超过MAXIMUM_CAPACITY,会将MAXIMUM_CAPACITY赋值给initialCapacity
                initialCapacity = MAXIMUM_CAPACITY;
        	// 判断负载因子loadFactor是否小于等于0或者是否是一个非数值
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                // 如果满足上述其中之一,则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
         	// 将指定的负载因子赋值给HashMap成员变量的负载因子loadFactor
            this.loadFactor = loadFactor;// 一般不建议修改默认的负载因子
            this.threshold = tableSizeFor(initialCapacity);
        }
    	// 最后调用了tableSizeFor,来看一下方法实现:
         /*
         	返回比指定cap容量大的最小2的n次幂数:
         	前面第一遍讲述的应该有些小伙伴难以理解,这里我在举例解析一下:
         	-------------------------------------------------------
         	首先假定传入的cap = 10
         	则,n = 10 -1 => 9
         	n |= n >>> 1 就等同于 n = (n | n >>> 1),所以:
         	(位运算不懂的可以去看我的《Java基础提高之位运算》这篇文章)
         	9 => 0b1001    9 >>> 1 => 0b0100 
         	n |= n >>> 1;  ===>  0b1001 | 0b0100 => 0b1101
         	n |= n >>> 2;  ===>  0b1101 | 0b0011 => 0b1111
            n |= n >>> 4;  ===>  0b1111 | 0b0000 => 0b1111
            n |= n >>> 8;  ===>  0b1111 | 0b0000 => 0b1111
            n |= n >>> 16; ===>  0b1111 | 0b0000 => 0b1111
            得到:
            0b1111 => 15
            返回:
            return 15 + 1 => 16
            -------------------------------------------------------
            如果cap 不减去1,即直接使n等于cap的话,int n = cap;
            我们继续用上边返回的cap => 16 传入tableSizeFor(int cap):
            
            cap = 16
            n = 16
            16 => 0b10000  16 >>> 1 => 0b01000
            n |= n >>> 1;  ===>  0b10000 | 0b01000 => 0b11000
            n |= n >>> 2;  ===>  0b11000 | 0b00110 => 0b11110
            n |= n >>> 4;  ===>  0b11110 | 0b00001 => 0b11111
            n |= n >>> 8;  ===>  0b11111 | 0b00000 => 0b11111
            n |= n >>> 16; ===>  0b11111 | 0b00000 => 0b11111
            得到:
            0b11111 => 31
            返回 return 31 +1 => 32
            
            而实际情况是应该传入cap = 16 , n = cap -1 = 15
            15 => 0b1111 
            
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            经过上面运算后得到:还是15
            
            返回结果:
            return 15 + 1 = 16
            所以我们得出结果:
            防止 cap 已经是 2 的幂数情况下。没有这个减 1 操作,
            则执行完几条无符号位移或位运算操作之后,返回的cap(32)将是实际所需cap(16)的 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;
        }
    
    
    

    说明:
    对于this.threshold = tableSizeFor(initialCapacity); 疑问?
    tableSizeFor(initialCapacity)**判断指定的初始化容量是否是2的n次幂,如果不是那么会变为比指定初始化容量大的最小的2的n次幂。

    但是注意,在tableSizeFor方法体内部将计算后的数据返回给调用这里了,并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug,应该这样书写:
    this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;

    这样才符合threshold的意思(当HashMap的size到达threshold这个阈值时会扩容)

    但是请注意,在jdk8以后的构造方法中,并没有对table这个成员变量进行初始化,table的初始化被推迟到了put方法中,在put方法中会对threshold重新计算。

    HashMap(Map<? extends K, ? extends V> m)

    包含另一个 “Map” 的构造函数

    // 构造一个映射关系与指定 Map 相同的新 HashMap。
    public HashMap(Map<? extends K, ? extends V> m) {
        	// 负载因子loadFactor变为默认的负载因子0.75
             this.loadFactor = DEFAULT_LOAD_FACTOR;
             putMapEntries(m, false);
     }
    
    

    最后调用了 putMapEntries(),来看一下方法实现:

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        //获取参数集合的长度
        int s = m.size();
        if (s > 0) {//判断参数集合的长度是否大于0
            if (table == null) { // 判断table是否已经初始化
                    // 未初始化,s为m的实际元素个数
                    float ft = ((float)s / loadFactor) + 1.0F;// 得到新的扩容阈值
                    int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 新的扩容阈值float自动向下转型为int
                
                    // 计算得到的t大于阈值,则初始化阈值,将其变为符合要求的2的n次幂数
                    if (t > threshold)
                        threshold = tableSizeFor(t);
            }
            // 如果table已初始化过了,并且m元素个数大于阈值,进行扩容处理
            else if (s > threshold)
                resize();
            // 将m中的所有元素添加至HashMap中
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                // 得到的key 和 value 放入 hashmap
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
    
    

    注意:

    float ft = ((float)s / loadFactor) + 1.0F; 这一行代码中为什么要加 1.0F ?

    (float)s/loadFactor 的结果是小数,加 1.0F 与 (int)ft 相当于是对小数做一个向上取整以尽可能的保证更大容量,更大的容量能够减少 resize 的调用次数(为了效率,应当尽量减少扩容的次数)。所以 + 1.0F 是为了获取更大的容量。
    例如:原来集合的元素个数是 6 个,那么 6/0.75 是8,由于8是 2 的n次幂,那么
    if (t > threshold) threshold = tableSizeFor(t);执行过后,新的数组大小就是 8 了。然后原来数组的数据就会存储到长度是 8 的新的数组中了,这样会导致在存储元素的时候,容量不够,还得继续扩容,那么性能降低了,而如果 +1 呢,数组长度直接变为16了,这样可以减少数组的扩容。

    展开全文
  • HashMap底层原理

    2019-09-28 11:52:32
    HashMap底层原理
  • HashMap底层实现原理及面试问题

    万次阅读 多人点赞 2018-08-29 11:00:56
    HashMap的工作原理 HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取...
  • 一:HashMap概述 HashMap存储的是key-value的键值对,允许key为null,也允许value为null。HashMap内部为数组+链表的结构,会根据key的hashCode值来确定数组的索引(确认放在哪个桶里),如果遇到索引相同的key,桶的...
  • HashMap底层实现原理(上)

    千次阅读 2020-03-30 17:23:05
    但是在JDK1.8后对HashMap进行了底层优化,改为了由数组+链表+红黑树实现,主要的目的是提高查找效率。 JDK版本 实现方式 节点数>=8 节点数<=6 1.8以前 数组+单向链表 数组+单向链表 数组+...
  • Java的HashMap底层实现原理(jdk1.8)

    千次阅读 2020-06-10 21:36:53
    标记:vivo 提前批大数据开发岗问到HashMap底层实现原理,回答的很烂,所以作此知识点的补充,以后在遇到java 的这些高频知识点,争取能够流利的回答出来。 在jdk1.6 1.7中,HashMap 采用位 |桶(容量)+链表实现...
  • HashMap 底层实现原理

    2021-08-02 17:09:33
    要了解HashMap底层实现原理,我们首先要对HashMap的部分底层源码进行分析 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable 我们可以...
  • 到了JDK1.8之后采用的是数组+链表+红黑树2.HashMap实现原理1.put()方法。2.get()方法。3.HashMap源码分析 HashMap在面试中经常被问到,今天就对hashMap的底层源码进行分析和解释 1.HashMap底层采用的存储结构 1.在...
  • 在java8中hashmap底层数据结构是Node数组,Node数组的数据结构是链表,当链表达到一定长度(8)将转为红黑树,这也是为什么说java8中hashmap是由数组+链表+红黑树组成。
  • Hashmap底层实现原理(get\put\resize) Hashmap怎么解决hash冲突? Hashmap是线程安全的吗? … 今天就从源码角度一探究竟。笔者的源码是OpenJDK1.7 2. 构造方法 首先看构造方法的源码 // 默认初始容量 static ...
  • hashmap 底层实现原理

    2021-03-04 11:06:45
    Java HashMap底层实现原理 HashMap底层是哈希表(散列表),哈希就是一个数组,数组的每个元素是一个单向链表。 ● 在第一次执行put方法时,给哈希表的数组(哈希桶)默认初始化,容量: 16 ● hashMap加载因子是0.75 ● ...
  • 下面介绍基于jdk1.8深入了解HashMap底层原理。 HashMap数据结构 HashMap实际是一种“数组+链表”数据结构。在put操作中,通过内部定义算法寻止找到数组下标,将数据直接放入此数组元素中,若通过算法得到的该数组...
  • HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。Entry是HashMap中的一个静态内部类。代码如下 //HashMap的主干数组,可以看到就是一个Entry数组,初始值...
  • 参考以下博文,很详细! https://www.cnblogs.com/little-fly/p/7344285.html
  • hashmap数组和链表的结合体 1、HashMap 是不是有序的?不是有序的。 2、有没有有序的Map实现类呢?有 TreeMap 和 LinkedHashMap。 3、然后问TreeMap 和 LinkedHashMap 是如何保证它的顺序的? TreeMap 是通过实现 ...
  • 今天我将给大家讲解一下HashMap底层实现原理和机制。相信大家不管在面试大公司还是小公司也好,都会经常被问道HashMap的实现原理,可能有的小伙伴上来就说:“啊,我知道!HashMap1.7是数组加链表,1.8是数组加链表...
  • Java中HashMap底层实现原理(JDK1.8)源码分析

    万次阅读 多人点赞 2016-06-05 11:13:44
    这几天学习了HashMap底层实现,但是发现好几个版本的,代码不一,而且看了Android包的HashMap和JDK中的HashMap的也不是一样,原来他们没有指定JDK版本,很多文章都是旧版本JDK1.6.JDK1.7的。现在我来分析一哈最新的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 66,857
精华内容 26,742
关键字:

hashmap底层实现原理