HashMap


一. 什么是哈希表

哈希表(hash table) 也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表。

其他数据结构在新增,查找等基础操作执行性能与哈希表对比:

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

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

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

  • 哈希表:相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下,仅需一次定位即可完成,时间复杂度为O(1)。

数据结构的物理存储结构只有两种:顺序存储结构链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组

比如要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。

这个函数可以简单描述为:存储位置 = f(关键字) ,这个函数f一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣。举个例子,比如要在哈希表中执行插入操作:

插入过程如下图所示:

查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。

哈希冲突

如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办

也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞

前面提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是,需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。

那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式。

二. HashMap基本使用

public class hashmapTest1 {
    public static void main(String[] args) {

        HashMap<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("a", "apple");//put设值
        hashMap.put("b", "boy");
        hashMap.put("c", "cat");

        System.out.println(hashMap);
        System.out.println(hashMap.size());//返回hashMap内key-value数量
        System.out.println("a:" + hashMap.get("a"));//get取值
        System.out.println(hashMap.containsKey("a"));//containsKey查找hashMap是否包含指定key
        System.out.println(hashMap.containsValue("apple"));//containsValue查找hashMap是否包含指定value
        System.out.println(hashMap.remove("b"));//remove移除hashMap中指定key的数据,没有指定key就返回null

        System.out.println(hashMap.keySet());//返回hashMap所有key
        System.out.println(hashMap.isEmpty());//判断hashMap是否为空
        
        //采用Iterator遍历HashMap
        Iterator it = hashMap.keySet().iterator();
        while(it.hasNext()) {
            String key = (String)it.next();
            System.out.println("key:" + key);
            System.out.println("value:" + hashMap.get(key));
        }

        //遍历HashMap的另一个方法
        Set<Map.Entry<String, String>> sets = hashMap.entrySet();
        for(Map.Entry<String, String> entry : sets) {
            System.out.print(entry.getKey() + ", ");
            System.out.println(entry.getValue());
        }
    }
}

三. HashMap的实现原理

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。(其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合)

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

Entry是HashMap中的一个静态内部类。代码如下:

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构
    int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    } 

简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的。

如果定位到的数组位置不含链表(当前entry的next指向null),那么查找,添加等操作很快,仅需一次寻址即可;

如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

3.1 HashMap的默认值

  • DEFAULT_INITIAL_CAPACITY

    默认的初始容量,必须是2的倍数。默认16也就是默认会创建 16 个箱子,箱子的个数不能太多或太少。如果太少,很容易触发扩容,如果太多,遍历哈希表会比较慢。

  • MAXIMUM_CAPACITY:哈希表最大容量,一般情况下只要内存够用,哈希表不会出现问题。

  • DEFAULT_LOAD_FACTOR:默认的负载因子。因此初始情况下,当键值对的数量大于 16 * 0.75 = 12 时,就会触发扩容,扩容到32。

  • TREEIFY_THRESHOLD:如果哈希函数不合理,即使扩容也无法减少箱子中链表的长度,因此 Java 的处理方案是当链表太长时,转换成红黑树。这个值表示当某个箱子中,链表长度大于 8 时,有可能会转化成树。

  • UNTREEIFY_THRESHOLD:在哈希表扩容时,如果发现链表长度小于 6,则会由树重新退化为链表。

  • MIN_TREEIFY_CAPACITY:在转变成树之前,还会有一次判断,只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期,多个键值对恰好被放入了同一个链表中而导致不必要的转化。

其中MAXIMUM_CAPACITY 为什么设置成1 << 30?

因为HashMap在确定数组下标Index的时候,采用的是( length-1) & hash的方式,只有当length为2的指数幂的时候才能较均匀的分布元素,所以HashMap规定了其容量必须是2的n次方。

而采用位运算<<来控制HashMap的大小,使用位运算同时还提高了Java的处理速度。 HashMap内部由Entry[]数组构成,Java的数组下标是由Int表示的。所以对于HashMap来说其最大的容量应该是不超过int最大值的一个2的指数幂,而最接近int最大值的2个指数幂用位运算符表示就是 1 << 30。

3.2 其他几个重要字段

查看hashmap源码:

  • transient int size:实际存储的key-value键值对的个数

  • int threshold:

    阈值,当table == {}时,该值为初始容量(初始容量默认为16);当table被填充了,也就是为table分配内存空间后,threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold。

  • final float loadFactor:

    • 负载因子,代表了table的填充度有多少,默认是0.75。

    • 负载因子存在的原因,还是因为减缓哈希冲突,如果初始桶为16,等到满16个元素才扩容,某些桶里可能就有不止一个元素了。

    • 所以负载因子默认为0.75,也就是说大小为16的HashMap,到了第13个元素,就会扩容成32。

  • transient int modCount:

    • HashMap被改变的次数,由于HashMap非线程安全,在对HashMap进行迭代时, 如果期间其他线程的参与导致HashMap的结构发生变化了(比如put,remove等操作), 需要抛出异常ConcurrentModificationException

四. JDK1.8中HashMap的性能优化

4.1 传统 HashMap的缺点

  • JDK 1.8 以前 HashMap 的实现是 数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。

  • 当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表有 n 个元素,遍历的时间复杂度就是 O(n),完全失去了它的优势。

  • 针对这种情况,JDK 1.8 中引入了红黑树(查找时间复杂度为 O(logn))来优化这个问题,即当链表超过8时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。

4.2 桶的树形化 treeifyBin()

在Java 8 中,如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 ),就使用红黑树来替换链表,从而提高速度。

这个替换的方法叫 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) {
        //如果哈希表中的元素个数超过了 树形化阈值,进行树形化
        // e 是哈希表中指定位置桶里的链表节点,从第一个开始
       TreeNode<K,V> hd = null, tl = null; //红黑树的头、尾节点
        do {
            //新建一个树形节点,内容和当前链表节点 e 一致
            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<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {

    return new TreeNode<>(p.hash, p.key, p.value, next);

 }

上述操作做了这些事:

(1)根据哈希表中元素个数确定是扩容还是树形化

(2)如果是树形化遍历桶中的元素,创建相同个数的树形节点,复制内容,建立起联系

(3)然后让桶第一个元素指向新建的树头结点,替换桶的链表内容为树形内容

4.3 HashMap的put方法

JDK1.7HashMap的put方法源码

public V put(K key, V value) {
    
    if (table == EMPTY_TABLE) {//如果table为空,则根据size的阈值填充,即为空则初始化
        inflateTable(threshold);
    }
    if (key == null){
        return putForNullKey(value);
    }
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    //遍历当前索引的冲突链,找是否存在对应的key
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //如果存在对应的key, 则替换oldValue并返回oldValue
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
	//冲突链中不存在新写入的Entry的key,则直接add
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

其中:if (key == null),则进入putForNullKey( )方法

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

putForNullKey()方法的执行逻辑为:

  • 遍历table并判断其中是否已经存在一个entry的key==null。

    • 如果已经存在则返回旧值并用新值替换。

    • 如果没有,则调用第三个方法:addEntry( )

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//扩容方法,原有基础上容量乘以2
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

addEntry()方法中看到首先根据thresholdtable中你所给出的桶索引位置是否为null来判断是否需要扩展map。不是要说的重点。 接下来不管扩不扩容,第四个方法createEntry()才是真正意义上的插入方法:

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

createEntry( )方法中可以看到,首先根据你给出的桶索引去到对应的entry e; 然后执行赋值:table[bucketIndex] = new Entry<>(hash, key, value, e); 那么这句就是把新的已经携带了你要添加的key和value值的entry添加到map中。 这句的关键就是第五个方法也就是new Entry<>的构建了:

Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

根据Entry的构造函数可以看出,把最后一个参数赋值给了next,而当前的k和value就是当前值。而n值就是原有的entry的完整值。 所以可以得出是添加到头部,而不是结尾处。

JDK1.8HashMap的put方法源码

public V put(K key, V value) {
    // 对key的hashCode()做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;
    // 步骤1:tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤2:计算index,并对null做处理
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 步骤3:节点key存在,直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 步骤4:判断该链为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 步骤5:该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //链表长度大于8转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // key已经存在直接覆盖value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
      // 步骤6:超过最大容量 就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

①.判断键值对数组table[i]是否为空或为null,否则执行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,如果超过,进行扩容。

附:HashMap put方法逻辑图(JDK1.8)

4.4 红黑树中查找元素 getTreeNode()

HashMap 在 JDK 1.8 中新增的操作: 红黑树中查找元素 getTreeNode()

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) {
        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;
}
  • (1)HashMap 的查找方法是 get(),它通过计算指定 key 的哈希值后,调用内部方法 getNode();

  • (2)这个 getNode() 方法就是根据哈希表元素个数与哈希值求模(使用的公式是 (n - 1) &hash)得到 key 所在的桶的头结点,如果头节点恰好是红黑树节点,就调用红黑树节点的 getTreeNode() 方法,否则就遍历链表节点。

  • (3)getTreeNode 方法使通过调用树形节点的 find()方法进行查找:

 final TreeNode<K,V> getTreeNode(int h, Object k) {
     
    return ((parent != null) ? root() : this).find(h, k, null);
     
}
  • (4)由于之前添加时已经保证这个树是有序的,因此查找时基本就是折半查找,效率很高。
  • (5)这里和插入时一样,如果对比节点的哈希值和要查找的哈希值相等,就会判断 key 是否相等,相等就直接返回;不相等就从子树中递归查找。

4.5 HashMap扩容机制

当hashmap中的元素越来越多的时候,碰撞的几率也就越来越高(因为数组的长度是固定的),所以为了提高查询的效率,就要对hashmap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,所以这是一个通用的操作。

Java 7 中Hashmap扩容机制

JAVA7扩容必须同时满足两个条件:

(1)存放新值的时候当前已有元素的个数必须大于等于阈值

(2)存放新值的时候当前存放数据发生hash碰撞(当前key计算的hash值换算出来的数组下标位置已经存在值)

因为扩容要同时满足上面这两个条件,所以存在下面这些情况:

  • 就是hashmap在存值的时候(默认大小为16,负载因子0.75,阈值12),可能达到最后存满16个值的时候,再存入第17个值才会发生扩容现象,因为前16个值,每个值在底层数组中分别占据一个位置,并没有发生hash碰撞。

  • 当然也有可能存储更多值(超或16个值,最多可以存26个值)都还没有扩容。

    • 原因:前11个值全部hash碰撞,存到数组的同一个位置(虽然hash冲突,但是这时元素个数小于阈值12,并没有同时满足扩容的两个条件。所以不会扩容),后面所有存入的15个值全部分散到数组剩下的15个位置(这时元素个数大于等于阈值,但是每次存入的元素并没有发生hash碰撞,也没有同时满足扩容的两个条件,所以叶不会扩容),前面11+15=26,所以在存入第27个值的时候才同时满足上面两个条件,这时候才会发生扩容现象。

Java 8 中Hashmap扩容机制

Java8不再像Java7中那样需要同时满足两个条件。

Java8中扩容只需要满足一个条件:当前存放新值(注意不是替换已有元素位置时)的时候已有元素的个数大于等于阈值(已有元素等于阈值,下一个存放后必然触发扩容机制)

即hashmap默认大小为16,负载因子0.75,阈值12;在java8中,当存入第13个值时必定触发扩容。

 注:

  (1)扩容一定是放入新值的时候,该新值不是替换以前位置的情况下(比如:put(“name”,"zhangsan"),而map里面原有数据<"name","lisi">,则该存放过程就是替换一个原有值,而不是新增值,则不会扩容)

  (2)扩容发生在存放后,即是数据存放后(先存放后扩容),判断当前存入对象的个数,如果大于阈值则进行扩容。

4.6 底层结构

  • Java7中Hashmap底层采用的是Entry对数组,而每一个Entry对又向下延伸是一个链表,在链表上的每一个Entry对不仅存储着自己的key/value值,还存了前一个和后一个Entry对的地址。

  • Java8中的Hashmap底层结构有一定的变化,还是使用的数组,但是数组的对象以前是Entry对,现在换成了Node对象(可以理解是Entry对,结构一样,存储时也会存key/value键值对、前一个和后一个Node的地址),以前所有的Entry向下延伸都是链表,Java8变成链表和红黑树的组合,数据少量存入的时候优先还是链表,当链表长度大于8,且总数据量大于64的时候,链表就会转化成红黑树,所以你会看到Java8的Hashmap的数据存储是链表+红黑树的组合,如果数据量小于64则只有链表,如果数据量大于64,且某一个数组下标数据量大于8,那么该处即为红黑树。

注:在jdk7中,当new Hashmap()的时候会对对象进行初始化,而jdk8中new Hashmap()并没有对对象进行初始化,而是在put()方法中通过判断对象是否为空,如果为空通过调用resize()来初始化对象。

源码分析
  • 作者:管理员(联系作者)
  • 发表时间:2020-03-28 19:29
  • 版权声明:自由转载-非商用-非衍生-保持署名(null)
  • undefined
  • 评论