Java-HashMap

摘要(未完)

查看了一下HashMap源代码,一些基本知识点

参考资料里面其实写的很好,建议看参考链接

概述

它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。

HashMap 大概具有以下特点:

除了不允许 null 并且同步,Hashtable 几乎和他一样。

HashMap内部结构

JDK1.7 中hashmap 是通过 桶(数组)加链表的数据结构来实现的。当发生hash碰撞的时候,以链表的形式进行存储。

JDK1.8 中hashmap 增加了在原有桶(数组) + 链表的基础上增加了黑红树的使用。当一个hash碰撞的数量超过指定次数(TREEIFY_THRESHOLD)的时候,链表将转化为红黑树结构。

负载因子

默认为0.75。一般不建议修改,

容量

默认

桶数默认为16,非常规设计(一般采用素数),主要是为了在取模和扩容时做优化,同时为了减少冲突。

设定

在构造hashmap时,如果你传入的是一个自己设定的数字,它会调用tableSizeFor帮你转换成一个比传入容量参数值大的最小的2的n次方(所以不管你传入什么数字最终还是2的幂)。

这里tableSizeFor如果你看过源代码的话,会发现用的是挺晦涩的位运算(强烈吐槽),下面一大堆的运算你可以理解为把这个数字的所有位都变为1,再加上1,就能得到比传入容量参数值大的最小的2的n次方

    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;
    }

MAXIMUM_CAPACIT

上面的MAXIMUM_CAPACIT的值是1 << 30

这个设定应该是考虑到int是4个字节,每个字节8位,就是32位,然后有一位是表示正负的,整数最大是(2^31)-1,但是选择小于等于2^30次而不是小于2^31,网上翻了一圈没找到答案,我姑且觉得就是其实无论是2^30也好,2^31也好,其实只是表示一个大概的峰值,实际项目中基本不会出现这种需求,所以具体数字是什么无所谓。

Hash

HashMap 中通过将传入键的 hashCode此值按位右移 16 位补零后的值进行按位异或,得到这个键的哈希值。

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

这里是由于,由于哈希表的容量都是 2 的 N 次方(最大2^30),在当前,元素的 hashCode() 在很多时候下低位是相同的,这将导致冲突(碰撞),因此 1.8 以后做了个移位操作:将元素的 hashCode() 和自己右移 16 位后的结果求异或。

由于 int 只有 32 位(4*8),无符号右移 16 位相当于把高位的一半移到低位:

ddd

扩容

参考资料

Java 8系列之重新认识HashMap

Comments

comments powered by Disqus