java8 的 hashmap 源码简单分析

雨翔河

首页列表关于

2019-01-24 15:05

>  原来的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比我还懒。

类型：工作标签：hashmap,java