Hashmap 源码分析之基础

public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
HashMap 继承于AbstractMap<K,V>，并实现map ，cloneable，serializable 接口。

在很多的源码中，我们都可以看到，一般都会继承一个Abstract...的抽象类。那么问题来了，为什么要这么做？

其实在正规框架中，接口一般是优于抽象类的，抽象类的存在是用来继承，但是Java中的类是不具有多继承的，抽象类作为类型定义受到了很大的限制。

而现有的类可以实现接口，多个接口，实现多种特性，如果要用抽象类实现，那么恐怕需要有层次的抽象类了。

在Java API，比较好的方案就是AbstractList,AbstractSet等抽象的骨架实现类。就是通过对于导出的每个重要的接口都提供一个抽象的骨架实现类，把接口和抽象类的优点结合起来。我们不必为了实现一个接口，去实现所有的方法，而是继承骨架实现类，它实现了部分基本操作，将需要子类实现的方法变成抽象方法，由子类去实现。但这个类有可能包含最简单的有效实现。

/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

这定义了默认的容量，一般为16，当然我们可以在初始化的时候设置大小，但内部实现是大于我们设计的数的必须为2的幂。最大是2^30.

/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

Hashmap的填充因子是默认是0.75；
当hashmap的填充达到75%的时候，会进行扩容。当然这个值我们可以初始化。但如果没有什么特殊要求，不要进行更改。

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

JDK1.8的源码比1.7的有改进。我们知道hashmap是用链地址法来解决冲突。

Paste_Image.png

（此图来源于网上）

我们从图中，看到了基本是这样实现的。但上述的两个值是链表转成树，树转成链表的临界值。红黑树 并不追求“完全平衡 ”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次。

在hashmap中其实是用了两种结构去存储entry，大于8的时候，转化成红黑树存储，在小于6的时候变成链表。这种变化，在性能极大的改变了hashmap的操作速度。（当然这个要有很大的数据量的情况，jdk1.8的hash设计非常的厉害，比较平均，这个结构其实我们平常一般是不会生成树，这个hash生成真的可以）

内部类
static class Node<K,V> implements Map.Entry<K,V>
这个类是用来存储结构的，我们都知道是一个数组加上链表或者红黑树生成的hashmap，而那个数组table就是

transient Node<K,V>[] table;

就是存储着这个内部类，红黑树是用

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>
实现的，其实LinkedHashMap.Entry<K,V> 继承于HashMap.Node<K,V>

Paste_Image.png

我们可以看到其实还有很多，比如我们经常遍历的使用的EntrySet Values KeySet这些其实就是hashmap遍历的时候返回的一些视图。

我们可以看到Node是静态成员类，用来表示外围类所代表的对象的组件。这个我们知道Entry对象对应于Map的每个键值对。但虽然每个entry都与一个map对应，但是entry上的方法getkey,getvalue其实是不需要访问map的。Entry对应上图的Node。
如果没有static关键字，该map其实也是可以工作的，只是买个entry都会有一个对该map的应用，这明显是会浪费空间和时间的。
像一些遍历器是用非静态成员变量实现的，因为他们每个实例都应该隐含着与外围类的一个外围实例所关联。

此文是读Effective java 和源码产生的
读源码，是我们了解大神领域的一大捷径
生命不息，奋斗不止