1. HashMap

HashMap是一个散列表，它存储的内容是 键值对映射，映射表不能有重复的键

HashMap实现了Map、Cloneable、Serializable接口

HashMap的实现不是同步的，这意味着 他不是线程安全的，他的key、value都可以为null。此外，它的 映射不是有序的。

HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”：

1.初始容量指的是 HashMap 集合初始化的时候自身的容量。可以在构造方法中指定；如果不指定的话，总容量默认值是 16 。需要注意的是初始容量必须是 2 的幂次方。

2.HashMap的最大容量不超过2的30次方

3.加载因子就是 HashMap (当前的容量/总容量) 到达一定值的时候，HashMap 会实施扩容。加载因子也可以通过构造方法中指定，默认的值是 0.75 。
举个例子，假设有一个 HashMap 的初始容量为 16 ，那么扩容的阀值就是 0.75 * 16 = 12 。也就是说，在你打算存入第 13 个值的时候，HashMap 会先执行扩容。

4.扩容阀值。即 扩容阀值 = HashMap 总容量 * 加载因子。当前 HashMap 的容量大于或等于扩容阀值的时候就会去执行扩容。扩容的容量为当前 HashMap 总容量的两倍。
比如，当前 HashMap 的总容量为 16 ，那么扩容之后为 32 。

Hash与Map的关系图：
HashMap与HashTable的底层实现原理及区别
从图中可以看出：
HashMap采用 数组+链表组成，数组是HashMap的主体，链表则是为了解决哈希冲突而存在的。

以下源码是基于JDK1.6的：

关于put()方法：

//HashMap部分源码
 public V put(K key, V value) {  
    if (key == null)  
        return putForNullKey(value);  
    int hash = hash(key.hashCode());  
    int i = indexFor(hash, table.length);  
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
        Object k;  
        //判断当前确定的索引位置是否存在相同hashcode和相同key的元素，如果存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。  
        //如果存在相同的hashcode，那么他们确定的索引位置就相同，这时判断他们的key是否相同，如果不相同，这时就是产生了hash冲突。  
        //Hash冲突后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 链。  
        //系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），  
        //那系统必须循环到最后才能找到该元素。  
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
            V oldValue = e.value;  
            e.value = value;  
            return oldValue;  
        }  
    }  
    modCount++;  
    addEntry(hash, key, value, i);  
    return null;  
}

重点：
hash值冲突是发生在put()时，先通过hash(key.hashCode())来获取hash值，然后通过indexFor(hash,table.length)获取数组的下标，先查询是否存在该hash值，若不存在，则直接以Entry<V,V>的方式存在数组之中，若存在，则对比Key值是否相同，若hash值和Key值都相同，则替换value值；若hash值相同，Key值不同，此时产生散列冲突，则形成一个单链表，将hash值相同，Key值不同的元素以Entry<V,V>的方式存在单链表中，这样就解决了Hash冲突，这种方法叫做分离链表法

与之类似的还有开放地址法。

关于get()方法：

public V get(Object key) {   
    if (key == null)   
        return getForNullKey();   
    int hash = hash(key.hashCode());   
    for (Entry<K,V> e = table[indexFor(hash, table.length)];   
        e != null;   
        e = e.next) {   
        Object k;   
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))   
            return e.value;   
    }   
    return null;   
}

从HashMap中get元素时，首先计算Key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法找到对应的元素(存在多个键值对)

关于HashMap中Hash的计算规则
HashMap中定位到桶的位置是根据Key的hash值与数组的长度取模来计算的

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

首先是取key的hashCode算法，然后对16进行异或运算和右移运算。

HashMap在1.7与1.8中的区别

JDK1.7中

使用一个Entry数组来存储数据结构，用key的hashCode值取模来决定key被放到数组的位置，如果hashcode相同，或者hashcode取模后的结果相同，那么这些key回别定位到Entry数组的同一个桶中，这些key形成一个单向链表。

在散列冲突特别多的情况下，这个链表会很长，那么put和get操作有可能要遍历整个链表，也就是说时间复杂程度最差情况下会退化到O(n)

JDK1.8中
使用一个Node数组来存储数据，但是这个Node可能是链表结构，也可能是红黑树结构
在散列冲突的情况下，如果同一个桶中的key不超过8个，使用链表来存储
如果超过8个，则调用函数treeifyBin，将链表转换为红黑树进行存储

2. HashTable与HashMap的异同

HashTable与HashMap都实现了Map接口，但是他们有一些区别：

继承的父类不同
HashMap继承自AbstractMap，而HashTable继承自Dictionary类，不过他们都实现了Serializable、Map、Cloneable这三个接口
对Null key和Null Value的支持不同
HashTable不支持Null值
HashMap中支持Null值，null作为主键，只有一个；但是null可以作为一个或多个键所对应的值。
线程安全性不同
HashTable是线程安全的，每个方法都加入了Synchronized，在多线程并发的环境下，可以直接使用HashTable
HashMap是线程不安全的，在多线程的环境下，可能产生死锁的问题，因此在使用HashMap时需要自己增加同步处理。
但是HashMap比HashTable的效率高很多
遍历方式的内部实现上不同
HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。

fail-fast机制是一种错误检测机制，它仅用来检测错误。
初始容量与每次扩充容量的大小不同
HashTable默认的初始容量为11，每次扩充变为原来的2n+1.
HashMap默认的初始容量为16，每次扩充为原来的2倍
计算hash值的方法不同
为了得到元素的位置，首先根据元素key计算出一个hash值，然后再用hash中计算最终的位置。

HashTable直接使用对象的hashCode。hashCode是根据对象的地址、或者字符串、或者数字计算出来的int类型的数值。然后再使用除留余数法来获得最终的位置

HashTable中的源码：

    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) %tab.length;

HashTable进行一次除法运算，比较耗时。
HashMap则将hash表的大小固定为2的幂，这样在取模运算时，不需要做除法，只需要做位运算，效率高。但是增加了散列冲突的概率。

对于HashMap与HashTable的缺点：ConcurrentHashMap类可以进行有效的解决，它采用的是分段锁的方法，可以保证的线程的安全性。
访问：https://www.cnblogs.com/ITtangtang/p/3948786.html

3. HashSet

HashSet是Set接口的典型实现，HashSet按照Hash算法来存储集合中的元素，存在以下特点：
不能保证元素的顺序，元素是无序的
HashSet不是同步的，在多线程并发环境下，他不是线程安全的
集合元素值允许为null

HashSet的构造方法：

//基于JDK1.8

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;
    //底层使用HashMap来保存所有的元素
    private transient HashMap<E,Object> map;

   // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
    private static final Object PRESENT = new Object();

   /** 
     * 默认的无参构造器，构造一个空的HashSet。 
     * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。 
     */  
    public HashSet() {
        map = new HashMap<>();
    }
    /** 
     * 构造一个包含指定collection中的元素的新set。 
     * 
     * 实际底层使用默认的加载因子0.75和足以包含指定 
     * collection中所有元素的初始容量来创建一个HashMap。 
     * @param c 其中的元素将存放在此set中的collection。 
     */  
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    /**
    * 以指定的initialCapacity和loadFactor构造一个空的HashSet。
    *
    * 实际底层以相应的参数构造一个空的HashMap。
    * @param initialCapacity 初始容量。
    * @param loadFactor 加载因子。
    */
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

     /**
    * 以指定的initialCapacity构造一个空的HashSet。
    *
    * 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。
    * @param initialCapacity 初始容量。
    */
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
    /**
    * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
    * 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。
    *
    * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
    * @param initialCapacity 初始容量。
    * @param loadFactor 加载因子。
    * @param dummy 标记。
    */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
 
    //此处省略部分源码
    
    // 将指定元素放入 HashSet 中，也就是将该元素作为 key 放入 HashMap 
    public boolean add(E e) 
    { 
        return map.put(e, PRESENT) == null; 
    } 

    // 调用 HashMap 的 remove 方法删除指定 Entry，也就删除了 HashSet 中对应的元素
    public boolean remove(Object o) 
    { 
        return map.remove(o)==PRESENT; 
    }

HashSet只是封装了一个HashMap对象来存储所有的集合元素，所有放入HashSet中的集合元素实际上由HashMap的key来保存，而HashMap的value则存储了一个PRESENT，他是一个静态的object对象。

HashSet的绝大部分方法是通过HashMap来实现的，因此HashSet和HashMap两个集合在实现本质上相同。

HashSet为什么要重写equals方法和hashcode方法？

第一: set集合没有顺序，不允许重复，即哈希码值一样的对象就是重复；但是在现实生活中，我们认为属性相同就是同一个对象，这与计算机中比较同一个对象的方法不同(计算机使用的是内存地址，即哈希码值)，于是我们就要重写equals方法和hashcode方法.

第二： 技术实现原理角度解释为什么要重写两个方法：程序向HashSet中添加一个对象的时候，先计算该对象的哈希值。比较：

1. 如果该对象的哈希值与集合中存在的对象的哈希值不一样，则判断没有重复，添加到集合中。

2. 如果该对象的哈希值与集合中存在的对象的哈希值一样，则通过equals方法来判断两个哈希值一样的对象是否为同一个对象:
判断的标准是属性是否相同， 1>，相同对象，不添加。 2>，不同对象，添加！

重写的目的是： 属性相同的不同对象在调用hashcode方法后返回相同的哈希码值，但是在重写的时候无法避免一个bug：有一些属性不同的对象也会返回相同的哈希码值，因此：在哈希码相同的时候，再用equals方法来比较两个对象的属性是否相同，这样确保万无一失。

AbstractSet源码：


  public boolean equals(Object o) {
        if (o == this)
            return true;

        if (!(o instanceof Set))
            return false;
        Collection<?> c = (Collection<?>) o;
        if (c.size() != size())
            return false;
        try {
            return containsAll(c);
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }

    public int hashCode() {
        int h = 0;
        Iterator<E> i = iterator();
        while (i.hasNext()) {
            E obj = i.next();
            if (obj != null)
                h += obj.hashCode();
        }
        return h;
    }

参考连接：
https://www.cnblogs.com/stevenczp/p/7028071.html
https://www.cnblogs.com/chengxiao/p/6059914.html

HashMap与HashTable的底层实现原理及区别

1. HashMap

2. HashTable与HashMap的异同

3. HashSet

相关推荐