首先是HashMap的学习，理解散列的概念以及相关的实现，并且会学习HashMap的源码，理解为什么HashMap的速度如此之快。

声明：参考到的资料在下方列出。

1.《Java编程思想》 作者BruceEckel

2.http://liujiacai.net/blog/2015/09/03/java-hashmap/#%E5%93%88%E5%B8%8C%E8%A1%A8%EF%BC%88hash-table%EF%BC%89

3.提前需要理解红黑树的知识，可以参考文章（写的非常的详细）：

http://www.cnblogs.com/skywang12345/p/3245399.html

 

一、优先级队列（这个知识点跟本文主题关系不大，但是整理记录一下，所以放在这里了）

直接上例子：

1 import java.util.PriorityQueue; 2  3 public class ToDoList extends PriorityQueue
     
      { 4  5     /** 6      *  7      */ 8     private static final long serialVersionUID = 1L; 9     static class TodoItem implements Comparable
      
        {10 11         private char primary;12         private int secondary;13         private String item;14         15         public TodoItem (String td, char pri, int sec) {16             this.item = td;17             this.primary = pri;18             this.secondary = sec;19         }20         @Override21         public int compareTo(TodoItem arg) {22             if (primary > arg.primary) {23                 return +1;24             }25             if (primary == arg.primary) {26                 if (secondary > arg.secondary) {27                     return +1;28                 } else if (secondary == arg.secondary){29                     return 0;30                 }31             }32             return -1;33         }34         35         public String toString() {36             return Character.toString(primary) + secondary + ": " + item;37         }38         39     }40     41     public void add(String td, char pri, int sec) {42         super.add(new TodoItem(td, pri, sec));43     }44     public static void main(String[] args) {45 46         ToDoList toDoList = new ToDoList();47         toDoList.add("Empty trash", 'C', 4);48         toDoList.add("Feed dog", 'A', 2);49         toDoList.add("Mow lawn", 'B', 7);50         toDoList.add("Water lawn", 'A', 1);51         while (!toDoList.isEmpty()) {52             System.out.println(toDoList.remove());53         }54     }55 56 }
      
     

我们可以看到，各项是如何按照我们给定的顺序进行排列的。

 

二、理解Map

Map的实现类有很多：

HashMap：（结构组成：数组+链表+红黑树）无序

TreeMap：基于红黑树的实现，使用红黑树的好处是能够使得树具有不错的平衡性。同时它是有序的，有序（但是按默认顺充，不能指定）

LinkedHashMap：有序的，它是Hash表和链表的实现，并且依靠着双向链表保证了迭代顺序是插入的顺序。

ConcurrentHashMap（一种线程安全的Map，不涉及同步加锁）、无序  .etc.

最常用的是HashMap，它的性能非常棒。至于如何棒，棒到什么程度，慢慢听我说。

性能是映射表的一个重要问题。我们使用散列码，可以代替缓慢的线性搜索，来提高HashMap的速度。散列码是相对唯一的，用以代表对象的int值（因为hashCode()是Object的方法，所以任何对象都可以生成散列码）。那么什么是散列码呢？在Map中，是通过散列来查找另一个对象的。它将键的信息保存在数组里（因为存储、查找元素最快的数据结构是数组），而数组的下角标就是hashCode()生成的散列码。数组的元素里存储的是键值得list。（为什么是list呢？因为数组的大小是不可变的，当Map存储的量很大时，key的数量肯定会超过数组的范围，因此用的list）。之后，取得list后，遍历其中的元素，用equal（）进行比较，最后得到我们的key。

总结查询一个值的过程。首先，计算散列码，然后使用散列码查询数组，之后，对数组中保存的list遍历，用equals（）方法进行线程的查询。这就是散列的原理，HashMap如此之快的原因。

使用HashMap存储我们的对象时，必须重写equals（）和hasCode().同时有以下几个注意点。

正确的equals（）方法必须满足下面5额条件‘：

1.自反性。对于任意x, x.equals(x)一定返回true；

2.对称性。对任意x，y， 如果x.equals(y)返回true，那么，y.equals(x)也返回true；

3.传递性。对任意x，y，z， 如果x.equals(y)返回true，y.equals(z)返回true，那么，x.equals(z)也返回true；

4.一致性。对任意x，y，如果对象中用于等价比较的信息没有改变，那么无论调用x.equals(y)多少次，结果必须一致，全是true，或全是false；

5.对任何不是null的x，x.equlas（null）一定是false。

注意的是，默认的Object.equlas()只是比较对象的地址。

下面说说hashCode的设计。

最重要的因素是：无论何时，对同一个对象调用hashCode（）都应该生成同样的值。同时，散列码要速度快，并且有意义。

 

我在这里上个图，大家可以更好的理解散列冲突的解决之道。（

图片出处：http://liujiacai.net/blog/2015/09/03/java-hashmap/#%E5%93%88%E5%B8%8C%E8%A1%A8%EF%BC%88hash-table%EF%BC%89）

左侧竖列为数组，数组角标就是哈希码，每个元素内，是个单向链表，用于解决数据冲突问题。

 

三、HashMap源码分析

源码版本是JDK1.8

1.初始化

1 /** 2      * Constructs an empty HashMap with the specified initial 3      * capacity and load factor. 4      * 5      * @param  initialCapacity the initial capacity 6      * @param  loadFactor      the load factor 7      * @throws IllegalArgumentException if the initial capacity is negative 8      *         or the load factor is nonpositive 9      */10     public HashMap(int initialCapacity, float loadFactor) {11         if (initialCapacity < 0)12             throw new IllegalArgumentException("Illegal initial capacity: " +13                                                initialCapacity);14         if (initialCapacity > MAXIMUM_CAPACITY)15             initialCapacity = MAXIMUM_CAPACITY;16         if (loadFactor <= 0 || Float.isNaN(loadFactor))17             throw new IllegalArgumentException("Illegal load factor: " +18                                                loadFactor);19         this.loadFactor = loadFactor;20         this.threshold = tableSizeFor(initialCapacity);21     }22 23     /**24      * Constructs an empty HashMap with the specified initial25      * capacity and the default load factor (0.75).26      *27      * @param  initialCapacity the initial capacity.28      * @throws IllegalArgumentException if the initial capacity is negative.29      */30     public HashMap(int initialCapacity) {31         this(initialCapacity, DEFAULT_LOAD_FACTOR);32     }33 34     /**35      * Constructs an empty HashMap with the default initial capacity36      * (16) and the default load factor (0.75).37      */38     public HashMap() {39         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted40     }

HashMap()的构造方法有三个。

第一个构造方法，需要传入容器大小值和负载因子。这个负载因子代表的是现有的容量size占容器size的比率，当超过这个设定的比率（默认是0.75）时，容器会自动扩容。

第二个构造方法（推荐使用），将容器大小传进去，这样我们根据业务量，给定一个合理大小的容器，可以避免以后，容量的扩容，提高效率。

第三个，不多说了，以前自己经常这么用，现在不了。

2.put（）

这个是肯定用到的了，放值，之后取值。

1     /** 2      * Associates the specified value with the specified key in this map. 3      * If the map previously contained a mapping for the key, the old 4      * value is replaced. 5      * 6      * @param key key with which the specified value is to be associated 7      * @param value value to be associated with the specified key 8      * @return the previous value associated with key, or 9      *         null if there was no mapping for key.10      *         (A null return can also indicate that the map11      *         previously associated null with key.)12      */13     public V put(K key, V value) {14         return putVal(hash(key), key, value, false, true);15     }

 

1     /** 2      * Computes key.hashCode() and spreads (XORs) higher bits of hash 3      * to lower.  Because the table uses power-of-two masking, sets of 4      * hashes that vary only in bits above the current mask will 5      * always collide. (Among known examples are sets of Float keys 6      * holding consecutive whole numbers in small tables.)  So we 7      * apply a transform that spreads the impact of higher bits 8      * downward. There is a tradeoff between speed, utility, and 9      * quality of bit-spreading. Because many common sets of hashes10      * are already reasonably distributed (so don't benefit from11      * spreading), and because we use trees to handle large sets of12      * collisions in bins, we just XOR some shifted bits in the13      * cheapest possible way to reduce systematic lossage, as well as14      * to incorporate impact of the highest bits that would otherwise15      * never be used in index calculations because of table bounds.16      */17     static final int hash(Object key) {18         int h;19         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);20     }

hash（）算法，key不为null时，取【key的哈希值】与【其右移16位的数值】的异或运算。

算法为什么是这样？里面的道理我就不知道了，肯定是经过大量数学运算，得到的这个算法。（我对象总说我是文科的。。。）

1     /** 2      * Implements Map.put and related methods 3      * 4      * @param hash hash for key 5      * @param key the key 6      * @param value the value to put 7      * @param onlyIfAbsent if true, don't change existing value 8      * @param evict if false, the table is in creation mode. 9      * @return previous value, or null if none10      */11     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,12                    boolean evict) {13         Node
     
      [] tab; Node
      
        p; int n, i; // 判断节点数组是否为空，如果为空，初始化节点数组。14         if ((tab = table) == null || (n = tab.length) == 0)15             n = (tab = resize()).length; // 判断数组中的某个元素是否为空，如果为空，初始化，创建一个新的Node16         if ((p = tab[i = (n - 1) & hash]) == null)17             tab[i] = newNode(hash, key, value, null);18         else {19             Node
       
         e; K k; // 判断传进来的key值是否已经存在。通过hash值和key值得两重比较来判断                // 如果key已经存在，存储的Node信息不变20             if (p.hash == hash &&21                 ((k = p.key) == key || (key != null && key.equals(k))))22                 e = p; // 如果是TreeNode实例，就将key存入红黑树中保存。23             else if (p instanceof TreeNode)24                 e = ((TreeNode
        
         )p).putTreeVal(this, tab, hash, key, value);25             else {
                       // 如果是Node实例，那么将创建一个TreeNode用于管理key的信息。                    // 我猜想，如果用单项链表的话，查找key时，还是线性查找，可以通过Red black tree，将性能提升。26                 for (int binCount = 0; ; ++binCount) {27                     if ((e = p.next) == null) {28                         p.next = newNode(hash, key, value, null);29                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st30                             treeifyBin(tab, hash);31                         break;32                     }33                     if (e.hash == hash &&34                         ((k = e.key) == key || (key != null && key.equals(k))))35                         break;36                     p = e;37                 }38             }39             if (e != null) { // existing mapping for key40                 V oldValue = e.value;41                 if (!onlyIfAbsent || oldValue == null)42                     e.value = value;43                 afterNodeAccess(e);44                 return oldValue;45             }46         }47         ++modCount;48         if (++size > threshold)49             resize();50         afterNodeInsertion(evict);51         return null;52     }
        
       
      
     

上面分析，每个分支的目的，至于每一行的具体代码，以及里面算法的实现，无法简短的说清楚，有兴趣的话，可以自己查阅资料。

1 /** 2          * Tree version of putVal. 3          */ 4         final TreeNode
     
       putTreeVal(HashMap
      
        map, Node
       
        [] tab, 5                                        int h, K k, V v) { 6             Class
         kc = null; 7             boolean searched = false; 8             TreeNode
        
          root = (parent != null) ? root() : this;                // 往树结构中插入节点                // 遍历节点。代码中是红黑树算法具体代码实现。 9             for (TreeNode
         
           p = root;;) {10                 int dir, ph; K pk;11                 if ((ph = p.hash) > h)12                     dir = -1;13                 else if (ph < h)14                     dir = 1;15                 else if ((pk = p.key) == k || (k != null && k.equals(pk)))16                     return p;17                 else if ((kc == null &&18                           (kc = comparableClassFor(k)) == null) ||19                          (dir = compareComparables(kc, k, pk)) == 0) {20                     if (!searched) {21                         TreeNode
          
            q, ch;22 searched = true;23 if (((ch = p.left) != null &&24 (q = ch.find(h, k, kc)) != null) ||25 ((ch = p.right) != null &&26 (q = ch.find(h, k, kc)) != null))27 return q;28 }29 dir = tieBreakOrder(k, pk);30 }31 32 TreeNode
           
             xp = p;33 if ((p = (dir <= 0) ? p.left : p.right) == null) {34 Node
            
              xpn = xp.next;35 TreeNode
             
               x = map.newTreeNode(h, k, v, xpn);36 if (dir <= 0)37 xp.left = x;38 else39 xp.right = x;40 xp.next = x;41 x.parent = x.prev = xp;42 if (xpn != null)43 ((TreeNode
              
               )xpn).prev = x;44 moveRootToFront(tab, balanceInsertion(root, x));45 return null;46 }47 }48 }
              
             
            
           
          
         
        
       
      
     

。。。

其他的代码先不分析了。

 

文章暂时就简要的写到这里吧。有很多细节地方讲解的不到位，只是说明了一个大致的实现思路。里面算法的具体操作实现，以后遇到再做总结。

不足的地方，望前辈指正。

谢过！！！