java8的hashmap源码简单分析 计算机 内容发表于2017-06-19

原来的hashmap采用的是数组加链表的方式,关于java里面实现链表我前面的文章有提到过实现思路,使用静态链表。在java8里是采用了数组+链表+红黑树。

static final int TREEIFY_THRESHOLD = 8;

只要阀值超过了8,链表会转换为一棵平衡二叉查找树
数据结构的每一个小格子存储的数据为一个桶,桶后面存储的每一个数据为bin,这是java8里面的注释说这玩意儿叫bin。

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

capacity 为桶的容量,默认初始值为16,最大为,2^30==1073741824

static final int MAXIMUM_CAPACITY = 1 << 30;

当量变少的时候,树会转变为链表,也有一个阀值,当低于6的时候会变化为树来存储。

static final int UNTREEIFY_THRESHOLD = 6;

以前学习数据结构和算法的时候用c实现过简单的hashmap,那时候感觉挺有意思,记得有一次面试某公司的时候被问及hashset的实现原理,我那时候并没看源码,随口答的我不知道,但是如果是我的话会用hashmap去实现不用重复造轮子,面试官一脸不悦说感觉错了,场面一顿尴尬,当然不用说肯定挂了。。。
后来回家我去看了下hashset的源码,一脸懵逼的看到这个:

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

hashset的实现是彻头彻尾的用的hashmap来实现的,不是我懒,oracle比我还懒。