HashMap

实现原理

image.png

hashmap是由数组和链表共同组成的，数组的特点是插入慢读取快，链表的特点是插入快读取慢，hashmap结合两者优势，插入读取速度快。
先介绍一下Entry，Entry包括key、value、hash、next。
在put过程中，首先计算key的hash值，再根据hash及数组长度，算出当前key、value属于数组中的哪个元素，若此位置中没有元素则直接插入，若有元素则先根据hash值及key的值是否相等来决定是否替换当前已存在的value，若相等则替换，若不相等则将put的key、value放入当前数组中，并将原来的值作为next放入Entry中。
若key为null，则将此元素放置在数组的首位置，即table[0]。
get比较简单，通过key的hash和值来判断，先在数组中寻找，接着通过循环数组中的链表，不断获取Entry的next寻找，直接返回匹配的value。

HashMap不是同步的

HashSet

HashSet内部实现的是HashMap，其构造函数如下：

public HashSet() {
        map = new HashMap<>();
    }

add:

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

remove:

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

contains:

public boolean contains(Object o) {
    return map.containsKey(o);
}

HashTable

HashTable和HashMap差不多
不同点：
1、HashMap继承AbstractMap，HashTable继承Dictionary
2、HashMap允许key，value为null，HashTable不允许
3、HashMap线程不安全，HashTable安全，内部方法是synchronized，可多个线程使用