侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

HashMap原理探究

林贤钦
2020-05-23 / 0 评论 / 18 点赞 / 482 阅读 / 14,308 字
温馨提示:
本文最后更新于 2021-03-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

HashMap原理探究

1、准备

在学习HashMap之前,首先得对一些概念搞清楚,有助于理解源码

  • 数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为O(logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n)

  • 线性链表:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)

  • 二叉树:对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。

  • 位运算 (具体可以看百度百科)

    • and运算 &:相同位的两个数字都为1,则为1;若有一个不为1,则为0。

      00101 5

      11100 28

      ----------------(&;或者and)

      00100 4

    • xor运算 ^ : 相同位不同则为1,相同则为0。

      00101 5

      11100 28

      ----------------(^或者xor)

      11001 25

    • or运算 | : 相同位只要一个为1即为1

      00101 5

      11100 28

      ----------------(|或者or)

      11101 29

    • shl运算 <<< (左移) : a shl b就表示把a转为二进制后左移b位(在后面添b个0)。

      例如100的二进制为1100100,而110010000转成十进制是400,那么100 shl 2 = 400。

    • shr运算 >>(右移) : 和shl相似,a shr b表示二进制右移b位(去掉末b位),相当于a除以2的b次方(取整)

      和上面一样的例子,那么400 shr2 = 100。我们也经常用shr 1来代替div 2

2、HashMap集合简介

HashMap基于哈希表的Map接口实现,是以key-value存储形式存在,即主要用来存放键值对。

HashMap 的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。

  • DK1.8 之前:HashMap 由 数组+链表 组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突**(两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同)**而存在的(“拉链法”解决冲突)

    拉链法:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

  • JDK1.8 以后:HashMap是由数据+链表+红黑树, 当链表长度大于阈值(或者红黑树的边界值,默认为 8)并且当前数组的长度大于64时,此时此索引位置上的所有数据改为使用红黑树存储。

    注意:当链表长度大于8的时候,并不代表一定会扩容,HashMap会判断,如果链表长度大于8但是当前数组没有超过64,会采取扩容数组的机制,并且来重新计算Hash值

为什么链表长度大于阈值并且当前数组的长度大于64时,才将此索引的所有数据改为使用红黑树?

	目的是因为数组比较小,尽量避开红黑树结构,这种情况下变为红黑树结构,反而会降低效率,因为红黑树需要进行左旋,右旋,变色这些操作来保持平衡 。同时数组长度小于64时,搜索时间相对要快些。

接下来列举一些常见问题

  1. HashMap中hash函数是怎么实现的?还有哪些hash函数的实现方式?

    对于key的hashCode做hash操作,无符号右移16位然后做异或运算。 还有伪随机数法和取余数法。这2种效率都比较低。而无符号右移16位和异或运算效率是最高的。

  2. 当两个对象的hashCode相等时会怎么样?

    会产生哈希碰撞,若key值内容相同则替换旧的value.不然连接到链表后面,链表长度超过阈值8并且数组长度大于等于64就转换为红黑树存储。

  3. 何时发生哈希碰撞和什么是哈希碰撞,如何解决哈希碰撞?

    只要两个元素的key计算的哈希码值相同就会发生哈希碰撞。jdk8前使用链表解决哈希碰撞。jdk8之后使用链表+红黑树解决哈希碰撞。

  4. 如果两个键的hashcode相同,如何存储键值对?

    hashcode相同,通过equals比较内容是否相同。

    • 相同:则新的value覆盖之前的value

    • 不相同:则将新的键值对添加到哈希表中

  5. 在不断的添加数据的过程中,会涉及到扩容问题,当超出临界值(且要存放的位置非空)。

    扩容。默认的扩容方式:扩容为原来容量的2倍,并将原有的数据复制过来。

如果不了解HashMap源码,可能一脸懵逼,HashMap是怎么算出来的,扩容是怎么扩容的

这个后面一步一步解答,首先我们先了解HashMap的继承关系,构造方法 ,以及类的成员变量,我觉得,了解一个类,不应该一开始就往方法里面冲。先了解这些有助于我们理解

3、HashMap继承关系

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

说明:

  • Cloneable 空接口,表示可以克隆。 创建并返回HashMap对象的一个副本。
  • Serializable 序列化接口。属于标记性接口。HashMap对象可以被序列化和反序列化。
  • AbstractMap 父类提供了Map实现接口。以最大限度地减少实现此接口所需的工作。

通过上述继承关系我们发现一个很奇怪的现象, 就是HashMap已经继承了AbstractMap而AbstractMap类实现了Map接口,那为什么HashMap还要在实现Map接口呢?同样在ArrayList中LinkedList中都是这种结构。

据 java 集合框架的创始人Josh Bloch描述,这样的写法是一个失误。在java集合框架中,类似这样的写法很多,最开始写java集合框架的时候,他认为这样写,在某些地方可能是有价值的,直到他意识到错了。显然的,JDK的维护者,后来不认为这个小小的失误值得去修改,所以就这样存在下来了。

4、HashMap集合类的成员

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
 	//序列化id
    private static final long serialVersionUID = 362498820763181265L;
    //默认的初始容量是16 -- 1<<4相当于1*2的4次方---1*16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //最大的容量 ,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,当链表的值小于6则会从红黑树转回链表
    static final int UNTREEIFY_THRESHOLD = 6;
    //最小的红黑树容量要求
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    //它是保存HashMap的最主要的数据结构
    transient Node<K,V>[] table;
    //它保存缓存的映射关系集合。注意,keySet()和values()使用的是父类AbstractMap的属性。
    transient Set<Map.Entry<K,V>> entrySet;
    
    //HashMap中元素个数size
    transient int size;
    //修改次数modCount
    transient int modCount;
    //下一次进行resize的门限个数。即扩容
    int threshold;
    //负载因子
    final float loadFactor;
}

HashMap的负载因子为什么是0.75

**loadFactor**加载因子,是用来衡量 HashMap 满的程度,**表示HashMap的疏密程度,影响hash操作到同一个数组位置的概率**

loadFactor太大导致查找元素效率低,太小导致数组的利用率低,存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。

当HashMap里面容纳的元素已经达到HashMap数组长度的75%时,表示HashMap太挤了,需要扩容,而扩容这个过程涉及到 rehash、复制数据等操作,非常消耗性能。,所以开发中尽量减少扩容的次数,可以通过创建HashMap集合对象时指定初始容量来尽量避免。

5、构造方法

5.1、HashMap()

使用默认初始容量16与默认负载因子0.75构造一个空的HashMap。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

5.2、HashMap(int initialCapacity, float loadFactor)

传入初始容量和负载因子来构造一个空的HashMap

static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 当map容量达到这个阈值的时候,需要进行resize。
 */
int threshold;
 
public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小于0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    // 初始容量不能大于MAXIMUM_CAPACITY
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 校验负载因子合法性
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;
    // 计算下次resize的阈值
    this.threshold = tableSizeFor(initialCapacity);
}
//对于给定的目标容量,返回两倍大小的幂。
 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;
 }

为什么要对cap做减1操作?

这是为了防止,cap已经是2的幂。如果cap已经是2的幂, 又没有执行这个减1操作,则执行完后面的几条无符号右移操作之后,返回的capacity将是这个cap的2倍

假如我们传入的值是7,n=6,二进制就是 110

cap =7 , int n=cap -1;--->6

n|=n>>>1;

0110 n=6

0011 n>>>1

-------> |= or运算 | : 相同二进制位只要一个为1即为1。

0111 7

第一次运算结果为7

n |= n >>> 2;

0111 n=7

0001 n>>>2

0111 结果 7

后面的运算都是7,只要n不大于最大容量值,就rerun n+1=8

结论,构造方法传入容量,只要不大于最大容量值,都会变成靠近2的n次幂那个数

5.3、HashMap(int initialCapacity)

传入初始容量,通过默认负载因子构造一个空的HashMap,调用了HashMap(int initialCapacity, float loadFactor)构造方法。

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

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

根据已有的Map接口创建一个元素相同的HashMap,使用默认初始容量与默认负载因子。

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();//传入map的大小
        if (s > 0) {
            //判断数组是否为空
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            //是否大于边界值,大于就扩容
            else if (s > threshold)
                resize();
            //遍历map集合存入键值对
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

在上面也出现过hash(key)这个方法,这个是一个计算hash 的方法

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

key,是我们的键,如果key==null,那么放回0,这也就是为什么hashmap能储存null,重点是后面(h = key.hashCode()) ^ (h >>> 16);

key.hashCode()是调用Object中的public native int hashCode();获取哈希值,

假设我们的key是“111”,那么"111".hashCode()=48657,二进制就是1011 1110 0001 0001‬

key.hashCode()) ^ (h >>> 16)

1011 1110 0001 0001‬ h

0000 0000 0000 0000 h >>> 16

------>^相同位不同则为1,相同则为0。

0100 1110 0001 0001

可以看到,hashmap重写了计算hash值的方法

有没有发现一个问题?容量为什么必须是2的n次幂?

当向HashMap中添加一个元素的时候,需要根据key的hash值,去确定其在数组中的具体位置。HashMap为了存取高效,要尽量减少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在把数据存到哪个链表中的算法。

这个算法实际上就是取模,hash%length 但是计算机中直接求余效率不如位运算,所以源码中做了优化,使用 hash&(length-1),而实际上hash%length等于hash&(length-1)的前提是length是2的n次幂。

举例:

说明:按位与运算:相同的二进制数位上,都是1的时候,结果为1,否则为零。

例如长度为8时候,3&(8-1)=3 2&(8-1)=2 ,不同位置上,不碰撞;

例如长度length为8时候,8是2的3次幂。二进制是:1000
length-1 二进制运算: 0111

hash&(length-1) ----> 3&(8-1)=3

00000011 3 hash

00000111 7 length-1

---------->

00000011-----》3 数组下标

hash&(length-1) ----> 2&(8-1)=2

00000010 2 hash

00000111 7 length-1

---------->

00000010-----》2 数组下标

说明:上述计算结果是不同位置上,不碰撞;

例如长度为9时候,3&(9-1)=0 2&(9-1)=0 ,都在0上,碰撞了;

例如长度length为9时候,9不是2的n次幂。二进制是:00001001

length-1 二进制运算: 00001000

hash&(length-1) 3&(9-1)=0

00000011 3 hash

00001000 8 length-1

---------->

00000000-----》0 数组下标

hash&(length-1) 2&(9-1)=0

00000010 2 hash

00001000 8 length-1

00000000-----》0 数组下标

结论容量为什么必须是2的n次幂,因为容量是2的n次幂,可以使得添加的元素均匀分布在HashMap中的数组上,减少hash碰撞,避免形成链表的结构,使得查询效率降低!

6、成员方法

6.1、put方法,增加

public V put(K key, V value) {
    //hash方法介绍过了,hashmap自己重新计算hash值
    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为null或length长度为0则扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //②②②②②②如果哈希桶为null,则创建节点放在该桶内
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //③③③③③③如果桶内第一个元素hash相等,key相等,则更新此节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //④④④④④④判断是否为红黑树,若是则调用红黑树的putTreeVal
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //⑤⑤⑤⑤⑤⑤⑤循环链表
            for (int binCount = 0; ; ++binCount) {
                //知道下个节点为null时
                if ((e = p.next) == null) {
                    //增加节点
                    p.next = newNode(hash, key, value, null);
                    //如果桶内的节点是否大于8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //这个方法里还会判断总节点数大于64则会转换为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                //如果找到相等的节点则退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //只有找到相等节点是e不为null
        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;
}

①.判断键值对数组table[i]为null或者长度为0,否则执行resize()进行扩容;

②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;

④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

6.2、get取值的方法

public V get(Object key) {
    Node<K,V> e;
    //计算hash值,如果null就返回null不然就返回计算后的结果
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //②②②②②②如果表为null或长度为0,或者经过hash算法后得到的哈希桶为null,则直接返回null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //③③③③③③如果链表中的第一个节点元素相等则直接返回该Node
        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);
            //否则循环链表找到对应相等的元素,直到找到或下个节点为null
            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值
int hash=key.hashCode();

②.调用内部方法 getNode(),得到桶号(一般为hash值对桶数求模)first
((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null)

③.比较桶的内部元素是否与key相等,若都不相等,则没有找到。相等,则取出相等记录的value。

④.如果得到 key 所在的桶的头结点恰好是红黑树节点,就调用红黑树节点的 getTreeNode() 方法,否则就遍历链表节点。getTreeNode 方法使通过调用树形节点的 find()方法进行查找。由于之前添加时已经保证这个树是有序的,因此查找时基本就是折半查找,效率很高。

⑤.如果对比节点的哈希值和要查找的哈希值相等,就会判断 key 是否相等,相等就直接返回;不相等就从子树中递归查找。

6.3、扩容方法

扩容是Hashmap重点中的重点。也是最耗性能的操作。扩容的步骤是先对size扩大两倍,再对原先的节点重新经过hash算法得到新的索引值即复制到新的哈希桶里。最后得到新的table。

其中jdk8对扩容进行了优化,提高了扩容的效率。但在平常运用中尽量要避免让hashmap进行扩容,若已知hashmap中的元素数量,则一开始初始化hashmap时指定容量,这样就减少了hashmap扩容次数。

什么时候会进行扩容

场景1:哈希table为null或长度为0;

场景2HashMap中存储的k-v对数量超过了阈值**threshold**(容量*负载因子);

场景3:链表中的长度超过了TREEIFY_THRESHOLD(一般是8),但表长度却小于MIN_TREEIFY_CAPACITY(一般是64)。

6.4、Map遍历的几种方式

方式1:Iterator迭代器

Iterator<Entry<String, Integer>> iterator = testMap.entrySet().iterator();
while (iterator.hasNext()) {
    Entry<String, Integer> next = iterator.next();
    System.out.println(next.getKey() + ":" + next.getValue());
}

方式2:最常见的使用方式,可同时得到key、value值

for (Map.Entry<String, Integer> entry : testMap.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

方式3:使用foreach方式(JDK1.8才有)

testMap.forEach((key, value) -> {
    System.out.println(key + ":" + value);
});

方式4:通过key的set集合遍历(不推荐,性能低)

Set<String> set = testMap.keySet();
for (String key : set) {
    testMap.get(key);
}

7、解决 hash 冲突的常见方法

a. 链地址法:将哈希表的每个单元作为链表的头结点,所有哈希地址为 i 的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。

b. 开放定址法:即发生冲突时,去寻找下一个空的哈希地址。只要哈希表足够大,总能找到空的哈希地址。

c. 再哈希法:即发生冲突时,由其他的函数再计算一次哈希值。

d. 建立公共溢出区:将哈希表分为基本表和溢出表,发生冲突时,将冲突的元素放入溢出表。

HashMap 就是使用链地址法来解决冲突的(jdk8中采用平衡树来替代链表存储冲突的元素,但hash() 方法原理相同)。当两个对象的hashcode相同时,它们的bucket位置相同,碰撞就会发生。此时,可以将 put 进来的 K- V 对象插入到链表的尾部。对于储存在同一个bucket位置的链表对象,可通过键对象的equals()方法用来找到键值对。


18

评论区