发表文章

[最新] HashMap的实现原理(JDK8)

hjw110520 3月前 1

一、什么是hash

哈希算法

  1. 接受任意长度的二进制输入值,对输入值做换算(hash),最终给出固定长度的二进制输出值;

  2. Hash算法不是某个固定的算法,它代表的是一类算法,具体换算可能各不相同

哈希表

即散列表,一种数据结构,根据关键码值(Key value)而直接进行访问

给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数

哈希碰撞

根据上面对哈希表的定义,有一种情况是,对不同的关键字可能得到同一散列地址,即k1≠k2,但f(k1)=f(k2),这种情况就是哈希碰撞。

解决哈希碰撞

拉链法(hashmap的解决方式):
将键转换为数组的索引(0-M-1),但是对于两个或者多个键具有相同索引值的情况,将大小为M 的数组的每一个元素指向一个条链表,链表中的每一个节点都存储散列值为该索引的键值对,这就是拉链法

二、HashMap的实现

基于哈希表的数据结构

线程不安全

下面从代码上来分析HashMap的实现原理

1. HashMap的结构

//实体数组
transient Node<K,V>[] table;
//实体构造函数
static class Node<K,V> implements Map.Entry<K,V> {
    Node(int hash,K key,V value,Node<K,V> next){
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;//链表中下一个元素的引用
    }
}

由上面的代码可以看出HashMap的基本结构就是:

1.储存的结构是实体Node[],即一个Map.Entry。内部4个值,key-value键值对,hash值,以及指向下一个元素的引用next,构成链表。
2.实体Node再构成的一个数组 Node[] table
3.而这个结构正是我们上面提到的hash表的结构,并很明显是用拉链法来解决hash冲突

2. put

//使用树而不是列表的bin计数阈值
static final int TREEIFY_THRESHOLD = 8;

public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);
}

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

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab;
        Node<K,V> p; 
        int n, i;
        //数组tab为空则创建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //如果没有发生hash碰撞,则直接添加到数组tab中
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //发生了hash碰撞
        else {
            Node<K,V> e; K k;
            //是否hash值相同,且key值也相同,即节点已存在
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //hash值相同,且key值也相同
                e = p;
            //该链是TreeNode
            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);
                        break;
                    }
                    //遍历过程中发现节点已存在
                    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;
        // 超过load factor*current capacity,resize
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

由上述代码可以看出put的逻辑
1.对key的hashCode()做hash计算得到hash值
2.根据hash值计算出对应在哈希表的数组中Node[] table中的下标:index = (size - 1) & hash
3.如果该下标上没有存放Node,即没有发生hash碰撞,则存放到table的该下标上
4.如果该下标上已经有存放Node,即发生了hash碰撞,则存放到table的该下标的链表的尾部
5.如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD=8)则会把链表转换成红黑树
6.如果节点已经存在就替换节点的值oldValue为新值
7.如果table已经满了,则resize增加table的长度

3. 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;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //直接找到了节点对应在table中的下标
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            //判断该下标下第一个节点的key也相同,则直接返回
            return first;
        if ((e = first.next) != null) {
            //开始遍历链表
            if (first instanceof TreeNode)
                return
               //TreeNode ((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;
}

由上述代码可以看出get的逻辑
1.对key的hashCode()做hash计算得到hash值
2.根据hash值计算出对应在哈希表的数组中Node[] table中的下标
3.该下标上的第一个元素fristNode和要查找的key值做判断fristNode.key.equals(key),如果相同,返回
4.如果不相同,遍历链表直到Node.key.equals(key),返回

4. 扩容resize()

//临界值(HashMap实际能存储的大小),公式为(threshold = capacity * loadFactor),当hashmap中存储元素大于这个数时,就需要resize了
int threshold;
/** 负载因子,默认为0.75*/
final float loadFactor;
//默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//数组默认的大小,16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//数组最大的容量,2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //旧表大小不为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)
            //把新表的阀值设为旧表2倍
            newThr = oldThr << 1; // double threshold
    }
    //如果旧表的长度的是0,则初始化表
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        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;//新表赋值给table
    //如果旧表不为空,要把旧表的值转移到新表
    if (oldTab != null) {
        //遍历旧表
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //node没有链表则直接放在新表的e.hash & (newCap - 1)位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //e是treeNode,则拆树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //e有链表,拆链表
                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;
}

由上述代码可以看出reSize的逻辑
1.先判断旧表,如果没有旧表,则初始化一个默认大小的新表或者构造函数中传入过的initialCapacity大小的新表(默认大小16;阀值为12;16*0.75),
2.如果有旧表,则初始化一个新表,大小为旧表的两倍,阀值也是旧表的两倍
3.把旧表的值转移到新表

5. loadFactor和initialCapacity:

loadFactor负载因子,代表的是map的装填程度,构造函数中有

if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +loadFactor);

表示loadFactor必须是大于0的数字。

由前面的知识我们知道HashMap是有数组table和链表的来实现的

initialCapacity表示HashMap的初始化数组table的大小

而HashMap的实际容量 = initailCapacity*loadFactor

当HashMap的实际容量满的时候,才会进行resize扩充容量

由此可知loadFactor越大,则HashMap中table会填的越满,链表会越长,越容易发生hash碰撞,造成索引效率低下;反之则会越稀疏,但会造成空间浪费。

loadFactor根据情况进行设置(时间空间选择)

注意:initailCapacity的值系统会根据传入的值换算成比传入值大的最接近的2的n次方这是因为

table下标计算:index = (size - 1) & hash

如当数组长度为15的时候,hashcode的值会与size - 1=14(1110)进行“与”,那么最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大

6. 使用注意:

1.reSize()比较耗性能的(主要是旧表的值转移到新表),所以初始化的时候最好能初始化合适的大小
2.HashMap hashMap = new HashMap(1000); 初始化后的表的大小为1024,即总是比传入值大的最小的2的n次方。这是因为数组长度为2的n次方的时候,不同的key算得得index相同的几率较小,可以减少hash碰撞,从而提高效率
3.jdk8中,HashMap处理碰撞才增加了红黑树这种数据结构,当碰撞结点较少时,采用链表存储,当较大时(>TREEIFY_THRESHOLD=8个),采用红黑树存储这样碰撞后的查询由链表变为了红黑树,即时间复杂度有O(n)变为了O(logn)

相关推荐
最新评论 (0)
返回
发表文章
hjw110520
文章数
5
评论数
0
注册排名
1305998