Chinaunix首页 | 论坛 | 博客
  • 博客访问: 59986
  • 博文数量: 24
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 335
  • 用 户 组: 普通用户
  • 注册时间: 2019-10-09 17:06
文章分类
文章存档

2019年(24)

我的朋友

分类: Java

2019-10-17 11:56:03

讲到HashMap不得不讲到HashCode,百度HashCode,它的释义如下

哈希码并不是完全唯一的,它是一种算法,让同一个类的对象按照自己不同的特征尽量的有不同的哈希码,但不表示不同的对象哈希码完全不同。也有相同的情况,看程序员如何写哈希码的算法。

HashCode是用来在散列存储结构中确定对象的存储地址,HashMap正是利用HashCode来快速定位存储对象的。

上面说过HashCode并不是唯一的,他取决于设计的哈希算法,所以在HashMap会出现Hash冲突的情况,那HashMap是怎么处理这种问题的呢?答案是在产生冲突的地方使用链表和红黑树。

JDK1.8之前解决hash冲突使用的是链表,实际上初始化后的HashMap就是由长度为1的单向链表组成的数组,在发生hash冲突时,该节点的单向链表保存具有相同hashcode的对象。在JDK1.8之后,当节点的单向链表长度大于8时,改为使用红黑树,提高查找效率。

HashMap是日常开发中非常常用的容器,HashMap实现了Map接口,底层的实现原理是哈希表,HashMap不是一个线程安全的容器,jdk8HashMap做了一些改进,作为开发人员需要对HashMap的原理有所了解,现在就通过源码来了解HashMap的实现原理。

首先看HashMap中的属性

    //Node数组

    transient Node[] table;

     //当前哈希表中k-v对个数,实际就是node的个数

    transient int size;

    //修改次数

    transient int modCount;

    //元素阈值

    int threshold;

    //负载因子

    final float loadFactor;

这里的threshold = loadFactor * table.lengthhash表如果想要保持比较好的性能,数组的长度通常要大于元素个数,默认的负载因子是0.75,用户可以自行修改,不过最好使用默认的负载因子。

Node是用来存储KV的节点,每次put(k,v)的时候就会包装成一个新的Node, Node定义

    static class Node implements Map.Entry {

        //hash

        final int hash;

        final K key;

        V value;

        //hash & (capacity - 1) 相同的Node会形成一个链表

        Node next;

        Node(int hash, K key, V value, Node next) {

            this.hash = hash;

            this.key = key;

            this.value = value;

            this.next = next;

        }

    }

put操作

写入操作是map中最常用的方法,这里看看hashmapput方法代码

public V put(K key, V value) {

    return putVal(hash(key), key, value, false, true);

}

这里先计算keyhash值,然后调用putVal()方法,其中hash方法是内部自带的一个算法,会对keyhashcode再做一次hash操作

 

static final int hash(Object key) {

    int h;

    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

pubVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

                   boolean evict) {

        Node[] tab; Node p; int n, i;

        if ((tab = table) == null || (n = tab.length) == 0)

            n = (tab = resize()).length; //如果数组为空,先初始化一下

        if ((p = tab[i = (n - 1) & hash]) == null) //如果对应的数组为空的话,那么就直接new一个node然后塞进去

            tab[i] = newNode(hash, key, value, null);

        else { //如果有值,说明发生了冲突,那么就先用拉链法来处理冲突

            Node e; K k;

            if (p.hash == hash &&

                ((k = p.key) == key || (key != null && key.equals(k))))

                e = p; //如果头结点的key和要插入的key相同,那么就说明找到了之前插入的节点

            else if (p instanceof TreeNode) //如果链表转成了红黑树

                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);

            else {

                for (int binCount = 0; ; ++binCount) {

                    if ((e = p.next) == null) { //如果之前没有put过这个节点,那么就new一个新的节点

                        p.next = newNode(hash, key, value, null);

                        if (binCount >= TREEIFY_THRESHOLD - 1)

                        //另外要检查一下当前链表的长度,如果超过8那么就将链表转化成红黑树

                            treeifyBin(tab, hash);

                        break;

                    }

                    if (e.hash == hash &&

                        ((k = e.key) == key || (key != null && key.equals(k))))

                        //如果找到了之前的节点,那么就跳出

                        break;

                    p = e;

                }

            }

            if (e != null) {

                V oldValue = e.value;

                if (!onlyIfAbsent || oldValue == null)

                    e.value = value;

                afterNodeAccess(e); //在当前类中NOOP

                return oldValue;

            }

        }

        ++modCount;

        //如果当前元素数量大于门限值,就要resize整个hash表,实际上就是把数组扩大一倍,然后将所有元素重新塞到新的hash表中

        if (++size > threshold)

            resize();

        afterNodeInsertion(evict); //在该类中NOOP

        return null;

    }

hashtable中默认的出现冲突的时候就会将冲突的元素形成一个链表,当链表长度大于8的时候就会将链表变成一个二叉树,这是java8中做出的改进,因为在使用hash表的时候在key特殊的情况下最坏的时候hash表会退化成外汇返佣一个链表,那么原有的O(1)的时间复杂度就变成了O(n),性能就会大打折扣,但是引用了红黑树之后那么在最好的情况下时间复杂度就变成了O(log(n))

resize方法

final Node [] resize() {

......

//去掉了一些代码,只关注最核心的node迁移

//resize会新建一个数组,数组的长度是原来数组长度的两倍

    for (int j = 0; j < oldCap; ++j) {//遍历原来的数组

        Node e;

        if ((e = oldTab[j]) != null) {

            oldTab[j] = null;

            if (e.next == null)

                newTab[e.hash & (newCap - 1)] = e; //如果没有形成链表的话,就直接塞到新的hash表中

            else if (e instanceof TreeNode)

                ((TreeNode)e).split(this, newTab, j, oldCap); //红黑树操作??

            else { // preserve order

                Node loHead = null, loTail = null;

                Node hiHead = null, hiTail = null;

                Node next;

                do {

                    next = e.next;

                    if ((e.hash & oldCap) == 0) { //如果hash值小于oldCap的时候,那么就还在原来那个数组的位置,就把这个节点放到low链表中

                        if (loTail == null)

                            loHead = e;

                        else

                            loTail.next = e;

                        loTail = e;

                    }

                    else { //否则的话就是因为扩展数组长度,就把原来的节点放到high链表中

                        if (hiTail == null)

                            hiHead = e;

                        else

                            hiTail.next = e;

                        hiTail = e;

                    }

                } while ((e = next) != null);

                if (loTail != null) {

                    loTail.next = null;

                    newTab[j] = loHead; //low链表还放在原来的位置

                }

                if (hiTail != null) {

                    hiTail.next = null;

                    newTab[j + oldCap] = hiHead; //high链表放到j+oldCap位置上

                }

            }

        }

    }

}

resize操作就是创建一个先的数组,然后把老的数组中的元素塞到新的数组中,注意java8中的hashMap中数组长度都是2n次幂,24、、816.. 这样的好处就是可以通过与操作来替代求余操作。当数组扩大之后,那么每个元素所在的位置是可以预期的,就是要不就待在原来的位置,要不就是到j+oldCap位置上,举个栗子,如果原来数组长度为4,那么hash37 的元素都会放在index3的位置上,当数组长度变成8的时候,hash3的元素还待在index3的位置,hash7的元素此时就要放到index7的位置上。

resize操作是一个很重要的操作,resize会很消耗性能,因此在创建hashMap的时候最好先预估容量,防止重复创建拷贝。

另外hashmap也是非线程安全的,在多线程操作的时候可能会产生cpu100%的情况,主要的原因也是因为在多个线程resize的时候导致链表产生了环,这样下次get操作的时候就会容易进入死循环。

get方法()

get的实现比较简单

final Node getNode(int hash, Object key) {

    Node[] tab; Node first, e; int n; K k;

    if ((tab = table) != null && (n = tab.length) > 0 &&

        (first = tab[(n - 1) & hash]) != null) {

        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) //如果节点不为空而且头结点与查找的key相同就返回

            return first;

        if ((e = first.next) != null) {

            if (first instanceof TreeNode)

                return ((TreeNode)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); //遍历链表查找key相同的node

        }

    }

    return null;

}

HashMap的常量和构造函数

    //默认初始容量,这个值必须是2的次幂    

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

    //最大容量,也必须设置成2的次幂  

    static final int MAXIMUM_CAPACITY = 1 << 30; // 1 073 741 824

    //负载因子默认大小

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //节点保存数据数量超过这个值,由链表转为红黑树

    static final int TREEIFY_THRESHOLD = 8;

    //当节点保存数据数量小于该值,红黑树转为链表存储

    static final int UNTREEIFY_THRESHOLD = 6;

    //红黑树最小长度

    static final int MIN_TREEIFY_CAPACITY = 64;

    //HashMap中实际就是用这样一个元素类型为Node的数组来存储数据,该数组长度必须为2的次幂

    //每个Node本质上就是一个单向链表

    transient Node[] table;

    //HashMap大小,它代表HashMap保存的键值对的多少

    transient int size;

    //HashMap被改变的次数

    transient int modCount;

    //HashMap扩容的阈值,保存键值对个数大于它就要扩容

    int threshold;

    //存储负载因子的常量

    final float loadFactor;

    public HashMap(int initialCapacity, float loadFactor) {

        if (initialCapacity < 0)

            throw new IllegalArgumentException("Illegal initial capacity: " +

                                               initialCapacity);

        if (initialCapacity > MAXIMUM_CAPACITY)

            initialCapacity = MAXIMUM_CAPACITY;

        if (loadFactor <= 0 || Float.isNaN(loadFactor))

            throw new IllegalArgumentException("Illegal load factor: " +

                                               loadFactor);

        this.loadFactor = loadFactor;

        this.threshold = tableSizeFor(initialCapacity);

    }

    public HashMap(int initialCapacity) {

        this(initialCapacity, DEFAULT_LOAD_FACTOR);

    }

    public HashMap() {

        this.loadFactor = DEFAULT_LOAD_FACTOR;

    }

    public HashMap(Map m) {

        this.loadFactor = DEFAULT_LOAD_FACTOR;

        putMapEntries(m, false);

    }

    final void putMapEntries(Map m, boolean evict) {

        int s = m.size();

        if (s > 0) {

            if (table == null) { // pre-size

                //根据loadFactor以及MAXIMUM_CAPACITY再次计算出新的threshold

                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();

            for (Map.Entry e : m.entrySet()) {

                K key = e.getKey();

                V value = e.getValue();

                putVal(hash(key), key, value, false, evict);

            }

        }

    }

HashMap中的元素单向链表NodeMap.Entry的实现,可以看到每一个Node只有next属性,没有pre属性,是一个单向链表

    static class Node implements Map.Entry {

        final int hash;

        final K key;

        V value;

        Node next;

        Node(int hash, K key, V value, Node next) {

            this.hash = hash;

            this.key = key;

            this.value = value;

            this.next = next;

        }

        public final K getKey()        { return key; }

        public final V getValue()      { return value; }

        public final String toString() { return key + "=" + value; }

        public final int hashCode() {

            return Objects.hashCode(key) ^ Objects.hashCode(value);

        }

        public final V setValue(V newValue) {

            V oldValue = value;

            value = newValue;

            return oldValue;

        }

        public final boolean equals(Object o) {

            if (o == this)

                return true;

            if (o instanceof Map.Entry) {

                Map.Entry e = (Map.Entry)o;

                if (Objects.equals(key, e.getKey()) &&

                    Objects.equals(value, e.getValue()))

                    return true;

            }

            return false;

        }

    }

HashMap中的红黑树也是自己实现的,这里就不详细列出其实现

static final class TreeNode extends LinkedHashMap.Entry {

    //省略...

}

HashMap主要常用API getput方法

    public V get(Object key) {

        Node e;

        return (e = getNode(hash(key), key)) == null ? null : e.value;

    }

    final Node getNode(int hash, Object key) {

        Node[] tab; Node first, e; int n; K k;

        //使用key参与hash运算后得出的hash,找出该位置的链表节点的第一个元素first

        if ((tab = table) != null && (n = tab.length) > 0 &&

            (first = tab[(n - 1) & hash]) != null) {

            //总是先检查链表第一个元素first是否匹配,匹配上就返回

            if (first.hash == hash &&

                ((k = first.key) == key || (key != null && key.equals(k))))

                return first;

            //匹配不上,就使用firstnext属性找到下一个节点e

            if ((e = first.next) != null) {

                //先判断第一个节点是否是红黑树节点,是则在红黑树中查找

                if (first instanceof TreeNode)

                    return ((TreeNode)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);

            }

        }

        //以上都无法匹配就返回null

        return null;

    }

    public V put(K key, V value) {

        return putVal(hash(key), key, value, false, true);

    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

                   boolean evict) {

        Node[] tab; Node p; int n, i;

        if ((tab = table) == null || (n = tab.length) == 0)

            n = (tab = resize()).length;

        //如果使用该hash计算出的位置没有元素,就把元素保存在这个位置

        if ((p = tab[i = (n - 1) & hash]) == null)

            tab[i] = newNode(hash, key, value, null);

        else {

            Node e; K k;

            //如果该位置有数据,且该节点Nodehashkey都与传入值相同或调用传入键对象的equals方法与节点Nodekey比较相同,则覆盖该数据

            if (p.hash == hash &&

                ((k = p.key) == key || (key != null && key.equals(k))))

                e = p;

            //如果上面的if判断不满足,且该位置节点Node是红黑树类型,使用红黑树保存

            else if (p instanceof TreeNode)

                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);

             //如果if满足也不是红黑树类型节点,则找出该位置单向链表最后一个位置的元素,把它的next指向新传入数据保存位置

            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;

                    }

                    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;

        //包含元素个数超过阈值,则扩容

        if (++size > threshold)

            resize();

        afterNodeInsertion(evict);

        return null;

    }

为什么HashMap的容量必须设置为2的次幂呢?

其实主要是为了在哈希算法中减少碰撞,使数据均匀分布。这里就不深究了。

阅读(45) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册