首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HashMap源码

HashMap源码

作者头像
小土豆Yuki
发布2020-06-15 17:13:41
4440
发布2020-06-15 17:13:41
举报
文章被收录于专栏:洁癖是一只狗洁癖是一只狗

解析HashMap源码,面试必备技能之一

目标

  1. 类继承关系
  2. HashMap属性认识
  3. HashMap底层数据结构
  4. HashMap源码解析get/put
  5. HashMap面试必问

一.类继承关系

二.HashMap属性

1.7JDK

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 1

    static final int MAXIMUM_CAPACITY = 1 << 30; //2

   static final float DEFAULT_LOAD_FACTOR = 0.75f; //3

    static final Entry<?,?>[] EMPTY_TABLE = {};

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

    transient int size; //5

    int threshold; //6

    final float loadFactor; //7

    transient int modCount; //8

1.数组的默认容量

2.最大容量

3.默认负载因子大小

4.hashMap的数组

5.当前数组存储的数量的大小

6.数组的大小(可在构造函数中初始化)

7.负载因子.可在构造函数中进行初始化

8.HashMap在结构上修改的次数

1.8JDK

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    static final int TREEIFY_THRESHOLD = 8;   //9

    transient Node<K,V>[] table; //10

和1.7的属性基本一样,不一样的是

9.判断是否使用红黑树

10.把1.7的Entry改成了Node

三.HashMap底层数据结构

1.7JDK

1.8JDK(数据结构做了优化)

四.HashMap源码解析get/put

1.7JDK中的Entry的定义

    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

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

每一个entry包含三个属性

key:map存储的key

value:map存储的value

next:指向下一个Entry对象

Put方法源码解析

public V put(K key, V value) {
    //1
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    //2
    if (key == null)
        return putForNullKey(value);
   //3
    int hash = hash(key);
   //4
    int i = indexFor(hash, table.length);
   //5
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
   //6
    addEntry(hash, key, value, i);
    return null;
}
}
  1. 判断是否为空,如果为空,进行初始化
  2. 如果key为null,设置key为null(HashMap是可以允许key和value可为null)
  3. key进行hash,获取hash值
  4. 根据hash值,获取数组下标
  5. 循环遍历数组,覆盖旧值,返回旧址
  6. 如果循环没有找到符合条件的,就进行添加新的Entry

get方法源码解析

public V get(Object key) {
    //1
    if (key == null)
        return getForNullKey();
   //2
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
   //3
    if (size == 0) {
        return null;
    }
   //4
    int hash = (key == null) ? 0 : hash(key);
   //5
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}
  1. 如果key为null,返回key对应的value
  2. 根据key返回的Entry
  3. 如果size为0,返回null
  4. key进行hash,返回hash值
  5. 根据hash值,返回数组下标,然后进行循环遍历获取对应的值

1.8JDK

put方法源码解析

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
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
       //2
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {

            Node<K,V> e; K k;
            //3
            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);
            else {
            //5 
                for (int binCount = 0; ; ++binCount) {
                  //6 
                   if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                  //7
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //8
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
         //9
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
  1. 判断当前数组是否为空,如果为空进行初始化
  2. 找到key对应的数组的值,判断你是否为null
  3. 如果找的的node不为空,判断hash值以及key是否相等,如果相等就返回
  4. 如果3不符合条件,判断是否是红黑树,如果是按照树的方式赋值
  5. 如果不是红黑树,循环遍历链表
  6. 找到下一个node,判断是否为null.如果为null,新建一个ndoe,再判断是超过阀值,如果超过就转变成红黑树
  7. 如果下一个node不为空,判断hash值以及key是否相等,如果相等返回,
  8. 如果e!=null,说明找到了hash值相等的值,覆盖旧的值
  9. 最后判断你是否扩容

get方法源码解析

public V get(Object key) {
    Node<K,V> e;
    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;
    //1
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //2
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
       //3
        if ((e = first.next) != null) {
            //4
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);          
            //5
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }//6
    return null;
}
  1. 先判断node数组是否为空
  2. 获取到节点,判断是否hash值和key是否相等.如果相等就返回
  3. 寻找下一个节点
  4. 判断节点是否是树节点,如果是,根据红黑树,返回节点值
  5. 判断节点是否符合条件相等,如果相等返回值
  6. 否则返回null

5.HashMap面试必问

HashMap 中没有两个相同的 key

在put源码中,且有一段循环遍历就是为了防止存在相同的 key 值,若发现两个 hash 值(key)相同时,HashMap 的处理方式是用新 value 替换旧 value,这里并没有处理 key

为什么数组的长度是2的n次方呢

 static int indexFor(int h, int length) {
     return h & (length-1);
 }

为了让数组的数据减少碰撞,就应该保持数据的均匀分布,一般均匀分布,我们会想到数组长度取模,但是由于取模的消耗较大就会使用上面的方式进行处理,因为数组的长度是2的n次方,所以h&(lenght-1)和取模的效果是一样的,

其中为什么是2的n次方,我们可以举个例子如下图

可以看到当数组长度是15的时候,计算的下表示有重复的,这样就会导致hash碰撞,形成链表,影响了查询值的效率,以及导致数据分布不均匀,因此当length=2^n的时候,会降低碰撞的概率,这样会使得数据分布均匀,以及提高查询性能。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-04-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 洁癖是一只狗 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档