public class LinkedList<E>extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    ////
}

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

2.判断该键值对是否已经存在于该下标值对应的桶中, 如果存在,则会覆盖老的value值,如果不存在,则会将该键值对添加到entry链表的表头.

**注意** 如果key为null, 则会将null key对应的键值对放在entry数组中下标为0的桶链表中.

通过指定的key获取HashMap中该key对应的value时会经历如下步骤

1.计算该key对应的键值对所在entry数组中的下标值,
2.遍历该下标对应的桶链表, 取出和参数key equals 的entry对应的value值

**注意** 如果key为null, 则HashMap会遍历entry数组下标为0的桶链表,找出key为null的entry节点并返回对应的value值.


### HashMap的扩展时机

HashMap默认的entry数组大小为16,负载因子为0.75.  如果HashMap中entry的数量和桶数组长度的比值大于负载因子
则HashMap会new一个2倍大小的桶数组,并重新分布所有的entry元素.


### HashMap是否是有序的

根据HashMap的实现原理,我们知道HashMap不是有序的,也就是说我们放入键值对的顺序和我们遍历HashMap取出键值对的顺序是不一致的.这个不难理解.

### 有序的Map实现类有哪些

有序的Map实现类有LinkedHashMap, TreeMap.



### HashMap和WeakHashMap的不同点

1. HashMap实现了Cloneable和Serializable接口，而WeakHashMap没有。HashMap实现Cloneable，意味着它能通过clone()克隆自己。HashMap实现Serializable，意味着它支持序列化，能通过序列化去传输。
2. HashMap的“键”是“强引用(StrongReference)”，而WeakHashMap的键是“弱引用(WeakReference)”。

WeakReference的“弱键”能实现WeakReference对“键值对”的动态回收。当“弱键”不再被使用到时，GC会回收它，WeakReference也会将“弱键”对应的键值对删除。这个“弱键”实现的动态回收“键值对”的原理呢？其实，通过WeakReference(弱引用)和ReferenceQueue(引用队列)实现的。 首先，我们需要了解WeakHashMap中：

* 第一，“键”是WeakReference，即key是弱键。
* 第二，ReferenceQueue是一个引用队列，它是和WeakHashMap联合使用的。当弱引用所引用的对象被垃圾回收，Java虚拟机就会把这个弱引用加入到与之关联的引用队列中。 WeakHashMap中的ReferenceQueue是queue。
* 第三，WeakHashMap是通过数组实现的，我们假设这个数组是table。

接下来，说说“动态回收”的步骤。
(01) 新建WeakHashMap，将“键值对”添加到WeakHashMap中。
将“键值对”添加到WeakHashMap中时，添加的键都是弱键。
实际上，WeakHashMap是通过数组table保存Entry(键值对)；每一个Entry实际上是一个单向链表，即Entry是键值对链表。
(02) 当某“弱键”不再被其它对象引用，并被GC回收时。在GC回收该“弱键”时，这个“弱键”也同时会被添加到queue队列中。
例如，当我们在将“弱键”key添加到WeakHashMap之后；后来将key设为null。这时，便没有外部外部对象再引用该了key。
接着，当Java虚拟机的GC回收内存时，会回收key的相关内存；同时，将key添加到queue队列中。
(03) 当下一次我们需要操作WeakHashMap时，会先同步table和queue。table中保存了全部的键值对，而queue中保存被GC回收的“弱键”；同步它们，就是删除table中被GC回收的“弱键”对应的键值对。
例如，当我们“读取WeakHashMap中的元素或获取WeakReference的大小时”，它会先同步table和queue，目的是“删除table中被GC回收的‘弱键’对应的键值对”。删除的方法就是逐个比较“table中元素的‘键’和queue中的‘键’”，若它们相当，则删除“table中的该键值对”。

### 正确遍历HashMap的姿势

```java
Map<String, String> map = new HashMap<String, String>();
map.put("apple", "苹果");
map.put("watermelon", "西瓜");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
   ////
}

List list = new ArrayList(map.entrySet());
    Collections.sort(list, new Comparator() {
        public int compare(Entry e1, Entry e2) {
            return e1.getKey().compareTo(e2.getKey());
        }
    });
}

SortedMap sortedMap = new TreeMap(new Comparator() {
    @Override
    public int compare(K k1, K k2) {
    return k1.compareTo(k2);
    }
});
sortedMap.putAll(map);

private static final Map map;
    static {
        map = new HashMap();
        map.put(1, "one");
        map.put(2, "two");
    }

private static final Map map;
static {
    Map map = new HashMap();
    map.put(1, "one");
    map.put(2, "two");
    map = Collections.unmodifiableMap(aMap);
}