A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 biu波儿了罢 于 2020-3-18 14:55 编辑

HashMap实现原理和扩容机制
1.实现原理:
HashMap的底层实现是一个哈希表即数组+链表;
HashMap初始容量大小16,扩容因子为0.75,扩容倍数为2;
HashMap本质是一个一定长度的数组,数组中存放的是链表。
       当向HashMap中put(key,value)时,会首先通过hash算法计算出存放到数组中的位置,比如位置索引为i,将其放入到Entry中,如果这个位置上面已经有元素了,那么就将新加入的元素放在链表的头上,最先加入的元素在链表尾。比如,第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起,也就是说数组中存储的是最后插入的元素。
      HashMap的get(key)方法是:首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。从这里我们可以想象得到,如果每个位置上的链表只有一个元素,那么hashmap的get效率将是最高的。所以我们需要让这个hash算法尽可能的将元素平均的放在数组中每个位置上

2.扩容机制
      当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容。
[Java] 纯文本查看 复制代码
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;      // HashMap初始容量大小(16) 
static final int MAXIMUM_CAPACITY = 1 << 30;               // HashMap最大容量
transient int size;                                       // The number of key-value mappings contained in this map
static final float DEFAULT_LOAD_FACTOR = 0.75f;          // 负载因子
HashMap的容量size乘以负载因子[默认0.75] = threshold;  // threshold即为开始扩容的临界值
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;    // HashMap的基本构成Entry数组

       当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过16*0.75=12(这个值就是代码中的threshold值,也叫做临界值)的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置。
       0.75这个值成为负载因子,那么为什么负载因子为0.75呢?这是通过大量实验统计得出来的,如果过小,比如0.5,那么当存放的元素超过一半时就进行扩容,会造成资源的浪费;如果过大,比如1,那么当元素满的时候才进行扩容,会使get,put操作的碰撞几率增加。
      HashMap中扩容是调用resize()方法,方法源码:
[Java] 纯文本查看 复制代码
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);
    table = newTable;
    //更新临界值
    threshold = (int)(newCapacity * loadFactor);
}
//旧数组中元素往新数组中迁移
void transfer(Entry[] newTable) {
    //旧数组
    Entry[] src = table;
    //新数组长度
    int newCapacity = newTable.length;
    //遍历旧数组
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);//放在新数组中的index位置
                e.next = newTable;//实现链表结构,新加入的放在链头,之前的的数据放在链尾
                newTable = e;
                e = next;
            } while (e != null);
        }
    }
}

       可以看到HashMap不是无限扩容的,当达到了实现预定的MAXIMUM_CAPACITY,就不再进行扩容。

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马