hashset和hashmap区别-HashMap底层实现原理是什么？

文章导读目录

三、hashMap工作原理

详细介绍一下java集合容器及hashMap工作原理

一、Collection 、Map

java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。

hashmap hashset 区别_hashset和hashmap区别_hashset和treeset区别

ArrayList：底层数组，排列有序可重复，速度快，增删慢，线程不安全，容量不够时，当前容量1.5倍+1；

Vector：底层数组，排列有序可重复，速度快，增删慢，线程安全，容量不够时，默认扩展一倍容量；

LinkedList：底层双向循环链表结构，排列有序，可重复，线程不安全，查询慢，增删快；

HashSet：底层哈希表，无序不可重复，内部是HashMap，存取速度快；

TreeSet：底层二叉树，排列无序不重复，排序存储，内部是TreeMap的SortedSet。

LinkedHashSet：底层哈希表，并用双向链表记录插入顺序，内部是

LinkedHashMap；

Queue：在两端出入的list，也可以用数组或者链表实现；

hashset和hashmap区别_hashmap hashset 区别_hashset和treeset区别

HashMap：底层哈希表，键不可重复，值可以重复，访问速度快，线程不安全，key、value都可以空，对应的线程安全的有ConcurrentHashMap；

HashTable：底层哈希表，键不可重复，值可以重复，线程安全，key、value都不可以空，使用了synchronized进行控制；

TreeMap：底层二叉树，键不可重复，值可以重复；实现了SortMap接口，默认按键值升序排序；也可以指定排序比较器；使用TreeMap时key必须实现Comparable接口或在构造TreeMap传入自定义的Comparator；

LinkedHashMap：是HashMap的一个子类，保存了记录的插入顺序；用Iterator遍历时，先取到的肯定是先插入的；

小结:tree开头的底层是二叉树；hash开头的底层是哈希表；set的内部其实还是map，link开头的底层是双向循环链表结构。

二、常见的问题 1、HashTable、HashMap、ConcurrentHashMap的区别？

HashTable：

ConcurrentHashMap：支持多线程

HashMap：

三、hashMap工作原理1、hashMap基本组成（数组+链表+红黑树）

HashMap的主干是一个Entry数组，链表则是主要为了解决哈希冲突而存在的（链表长度超过8变成红黑树，低于6变回链表；）；Entry是HashMap中的一个静态内部类。代码如下，包含4部分主要信息：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
    int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
    /**
         * Creates new entry.
         */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

注：hashcode是32位的int类型！

2、HashMap工作原理

1）HashMap通过put和get方法存储和获取；

2）存储对象时将K/V传给put（）；调用hash（）方法计算K的hash值，然后结合数组长度（n-1）& hash计算数组下标；

3）调整数组大小，容器中元素个数大于capacity*loadfactor时，容器自动扩容resize为2n；

4）如果k的hash值在hashmap中不存在，则插入，若存在，则碰撞；

5）如果k的hash值在hashmap中存在，切equals（）返回true，则更新键值对，若返回false，则插入链表的尾部（尾插法）或者红黑树中（树的添加方式），jdk1.7前是头插法；

6）获取对象时，将K传给get（）hashset和hashmap区别，调用hash（K）找到该键值所在的数组下标，若为链表，则在链表中通过key.equals(k)查找，O(n) ；若为树，则在树中通过key.equals(k)查找，O(logn)；

HashMap数组扩容过程：

创建一个新数组，容量为旧数组的两倍，重新计算旧数组中结点的位置，结点在新数组中的位置只有两种：

①原下标位置；②原下标位置+旧数组大小；

3、Hash函数的设计

将key的hashCode与该hashCode的无符号右移16位，异或起来得到的。

因为当table的size比较小时，能影响到table下标的，只有哈希值几个低位bit，这很可能会加剧哈希碰撞。但这样实现后，哈希值的高16位bit保持不变，低16位则受到高16位的“扰动”而发生改变，这样就使得高位bit也能影响table下标，减少哈希碰撞。

异或是因为：

key的hashCode只要有一个bit发生变化，hash函数的返回值也会跟着变化，用以减少哈希碰撞。

4、为什么计算下标用h & (length-1)？

作用上相当于取模mod或者取余%。

这意味着数组下标相同，并不表示hashCode相同。位操作肯定比取余操作快多了。

5、为什么重写了hashCode方法，也应该重写equals方法？

自定义的类作为key，hashCode方法和equals方法要么都不重写hashset和hashmap区别，要么都重写。

如果key只重写了hashCode方法，却没有重写equals方法。那么会造成map里会存在重复的我们认为“相同”的键值对在里面（一般是指，两个对象的成员是相同的）。因为如果添加了相同元素，根据put过程则发生哈希碰撞，本来这个相同元素不应该新增，但由于原始Object的equals方法逻辑使用==判断，所以只要地址值不同就肯定能添加进去。

如果key只重写了equals方法，却没有重写hashCode方法。那么也会造成map里会存在重复的我们认为“相同”的键值对在里面。因为使用了原始的hashCode了，有些该发生的哈希碰撞也就不会发生了，都不在一个哈希桶了，即使我们认为是“相同”的，也不会去调用你重写的equals方法的。

hashset和treeset区别_hashset和hashmap区别_hashmap hashset 区别