欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

哈?还在聊HashMap?老知识点了!

程序员文章站 2022-05-04 19:13:37
HashMap为什么经常被面试官问到,当然是它有“内涵”啊!【表情包】哈,原理我不知道?笑话!不就是一个hash加一个map嘛,百度一下不就ok了?答:利用key的hashCode重新hash计算出当前对象的元素在数组中的下标,存储到数组里面就行了,底层就是数组嘛!......

HashMap为什么经常被面试官问到,但是经常被面试官问趴下怎么办?

哈?还在聊HashMap?老知识点了!

哈,原理我不知道?笑话!

不就是一个hash加一个map嘛,多简单啊?
答:利用key的hashCode重新hash计算出当前对象的元素在数组中的下标,存储到数组里面就行了,底层就是数组嘛!
然后面试官说了句:好的,我知道了,回去听消息吧!

哈?还在聊HashMap?老知识点了!

这种答复并不是面试官想要看到的,想要听到程序员有自己的理解和分析优化!
今天就来给你们一探究竟,深挖HashMap!让你吊打面试官!

客官,来,1.7源码!

/**
*继承AbstractMap,并重写Map接口
**/
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
  
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 位运算,1左移4位=16
 static final int MAXIMUM_CAPACITY = 1 << 30;//位运算,左移30位=1073741824
 static final float DEFAULT_LOAD_FACTOR = 0.75f;//负载因子0.75
 transient Entry<K,V>[] table;//entry数组 entry又是个单链表结构
 transient int size;//hashmap长度
 int threshold;//capacity * load factor 阈值比如16*0.75 = 12
 void resize(int newCapacity)//扩容方法
 static int indexFor(int h, int length) {
    return h & (length-1);//计算index方法
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);//头插法解决hash冲突
    size++;
}

通过源码可以知道,HashMap的默认初始化长度为1 << 4=16,最大容量为1<<30=1073741824.
可以看出1.7是采用数组加单链表的结构,Entry是一个继承Map.Entry的单链表结构。size就是hashmap的长度,threshold就是插入扩容的阈值。
reSize方法可以看出,1.7是先进行扩容再插入数据的。

别着急,1.7是怎么进行扩容再插入的嘛!

容量初始值为16,当插入数据数量大于阈值(capacity * load factor=12)并发生hash冲突时就进行扩容。每次扩容都是2的n次幂,这样好处就是利于位运算,并且length-1的二进制最后一位为1,减少了hash碰撞。且插入时是通过int i = indexFor(e.hash, newCapacity);重新计算的,即hash & (length-1),并重新设置阈值(newCapacity * loadFactor)。

void resize(int newCapacity) {//扩容方法:resize(2 * table.length),当容量不足时(容量 > 阈值),则扩容(扩到2倍)
    Entry[] oldTable = table;//复制旧的哈希表
    int oldCapacity = oldTable.length;//旧的容量
    if (oldCapacity == MAXIMUM_CAPACITY) //容量如果等于最大值,则不再扩容
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(newTable, rehash);//转移数据到新哈希表里
    table = newTable;//完成扩容
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//重新设置阈值
}

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;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);//重新计算index值
            e.next = newTable[i];
            newTable[i] = e;//头部插入
            e = next;
        }
    }
}

还有1.8吗,太难了。挺住,坚持坚持就看完了!

哈?还在聊HashMap?老知识点了!

客官,还有1.8呢

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

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//Bins are converted to trees when adding an element to a bin with at least this many nodes.
static final int TREEIFY_THRESHOLD = 8;//当桶的节点数量大于该阈值时转换为红黑树
static final int UNTREEIFY_THRESHOLD = 6;//当桶的节点数小于该阈值时会转换成链表,前提是当前是红黑树结构
static final int MIN_TREEIFY_CAPACITY = 64;//桶的节点数大于该容量时也会转换成红黑树
static class Node<K,V> implements Map.Entry<K,V> ;//换成节点了
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>;//树节点
transient Node<K,V>[] table;//数组加单链表,后期会转红黑树
transient Set<Map.Entry<K,V>> entrySet;//数据的另一种存储方式,主要用于迭代功能
transient int size;//hashmap元素数量
transient int modCount;//该map的修改次数

从源码可以看出,初始容量还是16,负载因子还是0.75,只是多了关于红黑树的知识点。1.8采用数组加单链表加红黑树的数据结构,扩容还是扩2的n次幂。

hash方法:

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

通过判断key值是否为空,如果空就为0,不为空就异或运算。

存值方法put

public V put(K key, V value) {//存值
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //获取长度并进行扩容,使用的是懒加载,table一开始是没有加载的,等put后才开始加载
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)//(length-1)&hash计算出索引值,判断当前哈希桶是否为空
        tab[i] = newNode(hash, key, value, null);//空就赋值给当前桶
    else {//该哈希桶不为空,会发生hash冲突,以下为发生hash冲突几种情况
        Node<K,V> e; K k;
        //第一种情况,当前的hash值相同,且key值也相同,e = p表示首节点。
        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);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);//节点数大于等于7,则转换红黑树结构(从0开始到7)
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;//插入节点与next节点重复,跳出循环
                p = e;
            }
        }
        if (e != null) { //在节点中存在重复的值,直接覆盖旧值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;//修改次数加一
    if (++size > threshold)
        resize();//容量增一,判断是否需要扩容
    afterNodeInsertion(evict);//添加成功
    return null;
}

总的来说就是put的时候会进行判断当前桶是否为空,空就直接赋值。不为空且hash相同,则存在冲突,此时需要处理冲突的三种情况:
①当前桶不为空,且key值相同,则直接覆盖。
②当前桶不为空,则桶节点不为首节点,且为红黑树节点,则在红黑树中添加。(节点数>=TREEIFY_THRESHOLD)
③当前桶为不为空,不为首节点,不为红黑树节点,则为链表节点。(节点数<TREEIFY_THRESHOLD)添加时如果大于等于7(从0到7),则需要转为红黑树节点。

插入值过后就需要判断容量问题,此时就需要reSize()方法,从上述的源码中if (++size > threshold)就知道JDK1.8是先插入再进行判断扩容的。当链表深度大于8时,会自动扩容为红黑树结构,时间复杂度从O(n)转到O(logn)

final Node<K,V>[] resize() {//扩容方法
    Node<K,V>[] oldTab = table;//之前旧的哈希表
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;//old的表的阈值
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {//容量大于最大值
            threshold = Integer.MAX_VALUE;//此时阈值为整数最大值
            return oldTab;//最大限度 不能扩容了
        }//左移一位,新的哈希表扩容两倍,且要小于最大容量;且旧容量要比默认初始容量大
        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;//初始化的阈值
    else {               //容量为0,阈值就为容量*负载因子
        newCap = DEFAULT_INITIAL_CAPACITY;//默认初始容量16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//阈值16*0.75=12
    }
    if (newThr == 0) {//如果初始化容量小于16时,没有阈值。因为构造函数可以自己设初始容量
        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) {//当前哈希桶节点为e
                oldTab[j] = null;
                if (e.next == null)//没有下个节点
                    newTab[e.hash & (newCap - 1)] = e;//重新计算index,放入新的哈希表中
                else if (e instanceof TreeNode)//有next节点,且为树节点,将此树转移到新的cap中
                    ((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;//返回新的哈希表
}

总的来讲,插入数据后扩容过程分为以下几个步骤

①当前容量是否超过最大容量,超过则不扩容,直接返回。且阈值(threshold)为整数的最大值
②当前容量小于最大容量且大于初始容量。容量扩大两倍,阈值也扩大两倍

扩容后就将旧的表数据转移到新的表,利用hash&length-1计算index值,判断当前桶节点属于链表节点还是红黑树节点,再依次移入。

public V remove(Object key) {
    Node<K,V> e;//判断删除的节点是否为空,不为空就返回该节点值
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;//获取当前的节点
        else if ((e = p.next) != null) {//要删除的节点
            if (p instanceof TreeNode)//下一个节点为树节点
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {//链表节点,遍历找到节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }//遍历找到节点
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)//如果删除的是红黑树节点
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)//普通节点
                tab[index] = node.next;
            else//链表节点,修改next值
                p.next = node.next;
            ++modCount;//修改次数加一
            --size;//元素减一
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;//表示没有该节点,没找到
}

区别加总结

相同点:
计算index都是hash&length-1
不同点:
①JDK1.7时采用的是数组加单链表的数据结构,JDK1.8采用的是数组加单链表加红黑树的数据结构
②1.7是先扩容再插入,1.8是先插入再扩容
③解决冲突时,1.7是头插法的纵向延伸,但会容易逆序环形链表死循环问题;1.8是加入了红黑树,采用尾插法,能够避免出现逆序死循环的问题。

HashMap有哪些不足,怎么解决和优化

hashmap具有键-值(key-value)都允许为空、线程不安全、不保证有序、存储位置随时间变化的特性,即
哈?还在聊HashMap?老知识点了!

为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键

哈?还在聊HashMap?老知识点了!

HashMap 中的 key若 Object类型, 则需实现哪些方法?

哈?还在聊HashMap?老知识点了!
部分内容借鉴网址:https://www.jianshu.com/p/8324a34577a0?utm_source=oschina-app
确实写的好,佩服!

Hashmap确实还有很多可以深挖的知识点,这也是我第一次认真的写一篇文章,在我这么写了几千字的面子上就点个小心心呗,以后我会隔几天写一篇技术栈的文章并且同步到github上!有什么写的不好的地方和不足,欢迎大家指出!

哈?还在聊HashMap?老知识点了!
隔壁写的实在是太好了,导致我有点力不从心,就这样吧!

本文地址:https://blog.csdn.net/liyuanbo1997/article/details/107371483

相关标签: 笔记 hashmap