HashMap、HashSet、Hashtable的区别

突然发现整理了很多笔记，应该放这里做备用

Hashtable和HashMap

主要区别：线程安全性，同步(synchronization)，以及速度。

HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null。Hashtable是线程安全的，多个线程可以共享一个Hashtable。

HashMap的同步问题可通过Collections的一个静态方法得到解决，Map Collections.synchronizedMap(Map m) 返回一个同步的Map。

HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。fail-fast结构上更改时（删除或者插入一个元素），将会抛出ConcurrentModificationException异常。

HashMap不能保证随着时间的推移Map中的元素次序是不变的。

HashSet和HashMap的区别

HashSet实现了Set接口，它不允许集合中有重复的值，当我们提到HashSet时，第一件事情就是在将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，这样才能比较对象的值是否相等，以确保set中没有储存相等的对象。如果我们没有重写这两个方法，将会使用这个方法的默认实现。

Map中不允许重复的键。Map接口有两个基本的实现，HashMap和TreeMap。TreeMap保存了对象的排列次序，而HashMap则不能。HashMap允许键和值为null。

HashSet 和 HashMap 之间有很多相似之处，对于 HashSet 而言，系统采用 Hash 算法决定集合元素的存储位置，这样可以保证能快速存、取集合元素；对于 HashMap 而言，系统 key-value 当成一个整体进行处理，系统总是根据 Hash 算法来计算 key-value 的存储位置，这样可以保证能快速存、取 Map 的 key-value 对。

HashMap

public V put(K key, V value) {   
    // 如果 key 为 null，调用 putForNullKey 方法进行处理  
    if (key == null)   
        return putForNullKey(value);   
    // 根据 key 的 keyCode 计算 Hash 值  
    int hash = hash(key.hashCode());   
    // 搜索指定 hash 值在对应 table 中的索引  
    int i = indexFor(hash, table.length);  
    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素  
    for (Entry<K,V> e = table[i]; e != null; e = e.next)   
    {   
        Object k;   
        // 找到指定 key 与需要放入的 key 相等（hash 值相同  
        // 通过 equals 比较放回 true）  
        if (e.hash == hash && ((k = e.key) == key   
            || key.equals(k)))   
        {   
            V oldValue = e.value;   
            e.value = value;   
            e.recordAccess(this);   
            return oldValue;   
        }   
    }   
    // 如果 i 索引处的 Entry 为 null，表明此处还没有 Entry   
    modCount++;   
    // 将 key、value 添加到 i 索引处  
    addEntry(hash, key, value, i);   
    return null;   
}  

Map.Entry，每个 Map.Entry 其实就是一个 key-value 对。

当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。可以把 Map 集合中的 value 当成 key 的附属。

indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。

根据上面 put 方法的源代码可以看出，当程序试图将一个 key-value 对放入 HashMap 中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但 key 不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部。

Map提供了一些常用方法，如keySet()、entrySet()等方法，keySet()方法返回值是Map中key值的集合；entrySet()的返回值也是返回一个Set集合，此集合的类型为Map.Entry，接口中有getKey()、getValue方法。

内部实现

HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结构，但是在jdk1.8里 ，加入了红黑树的实现，当链表的长度大于8时，转换为红黑树的结构。

少于8个的时候，Java中HashMap采用了链地址法。

通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。

而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能。

indexFor方法一般想到的是把hash值对数组长度取模运算，但运算较大，因此1.7中使用以下方法，&比%具有更高的效率：

static int indexFor(int h, int length) { 
     return h & (length-1);  //第三步 取模运算
}

在JDK1.8的实现中，优化了高位运算的算法：(h = k.hashCode()) ^ (h >>> 16)

红黑树

红黑树（Red Black Tree） 是一种自平衡二叉查找树。红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间。

equals()和hashCode()

两个obj，如果equals()相等，hashCode()一定相等。
两个obj，如果hashCode()相等，equals()不一定相等（Hash散列值有冲突的情况，虽然概率很低）。

equals()和hashcode()这两个方法都是从object类中继承过来的。equals()是对两个对象的地址值进行的比较（即比较引用是否相同），hashCode()是一个本地方法，它的实现是根据本地机器相关的。

hashCode()在new的用途

JVM每new一个Object,它都会将这个Object丢到一个Hash哈希表中去,这样的话,下次做Object的比较或者取这个对象的时候,它会根据对象的hashcode再从Hash表中取这个对象。这样做的目的是提高取对象的效率。

如果不同的对象确产生了相同的hash值,也就是发生了Hash key相同导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将所有产生相同hashcode的对象放到这个单链表上去,串在一起。比较两个对象的时候,首先根据他们的hashcode去hash表中找他的对象，当两个对象的hashcode相同，只能根据Object的equal方法来比较这个对象是否equal。

重写equals()的原因

Object的equal方法默认是两个对象的引用的比较，意思就是指向同一内存。

但是，String对象中equals方法是判断值的，而==是地址判断（因为JDK重写了）。

我们很大部分时间都是进行两个对象的比较（而不是比较引用），这个时候Object的equals()方法就不可以了，所以才会有String这些类对equals方法的改写，依次类推Double、Integer、Math等等这些类都是重写了equals()方法的，从而进行的是内容的比较。

重写equals()后要重写hashCode()的理由

java.lnag.Object中对hashCode的约定：
1. 在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，则对该对象调用hashCode方法多次，它必须始终如一地返回同一个整数。
2. 如果两个对象根据equals(Object o)方法是相等的，则调用这两个对象中任一对象的hashCode方法必须产生相同的整数结果。
3. 如果两个对象根据equals(Object o)方法是不相等的，则调用这两个对象中任一个对象的hashCode方法，不要求产生不同的整数结果。但如果能不同，则可能提高散列表的性能。

只要改写了就会违约，所以要继续改写。

Hashtable与ConcurrentHashMap区别

ConcurrentHashMap融合了hashtable和hashmap二者的优势。hashmap在单线程情况下效率较高；hashtable在的多线程情况下，同步操作能保证程序执行的正确性。

hashtable每次同步执行的时候都要锁住整个结构：

ConcurrentHashMap锁的方式是稍微细粒度的。

更令人惊讶的是ConcurrentHashMap的读取并发，因为在读取的大多数时候都没有用到锁定，所以读取操作几乎是完全的并发操作，而写操作锁定的粒度又非常细，比起之前又更加快速（这一点在桶更多时表现得更明显些）。只有在求size等操作时才需要锁定整个表。

在迭代时，使用弱一致迭代器，不再是抛出 ConcurrentModificationException，在改变时new新的数据从而不影响原有的数据，iterator完成后再将头指针替换为新的数据。

常见问题

HashMap的工作原理，HashMap的get()方法的工作原理

答：“HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。”

关键：HashMap是在bucket中储存键对象和值对象，作为Map.Entry。

当两个对象的hashcode相同会发生什么

因为hashcode相同，所以它们的bucket位置相同，发生冲突，Entry(包含有键值对的Map.Entry对象)会存储在链表中。

hashcode相同如何获取值对象

遍历链表直到找到Entry对象，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点。

超过了负载因子(load factor)定义的容量

默认的负载因子大小为0.75，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小（rehashing）。当多线程的情况下，可能产生条件竞争(race condition)，两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。

先这样吧

若有错误之处请指出，更多地关注煎鱼。