1 还是老习惯，一边看，一边添加注释，希望坚持下去，HashMap的基本源码进行了分析，内部一些接口和设计还没来得及看  2   3 一、成员  4   5 1、transient Entry[] table;  6   7 HashMap内部维护了一个内部类-Entry，用来存放键值对，这个Entry实现了Map.Entry这一Map的内部接口Entry，HashMap本质上来讲是由数组和Entry链表组成的数据结构  8   9 2、 static final float DEFAULT_LOAD_FACTOR = 0.75f; 10  11 加载因子，加载因子越大，hash表（即Entry数组）所占空间越少，但会影响查询性能（因为需要通过链表一个挨一个向下查询），加载因子越小，hash表（即Entry数组）所占空间越多，这时查询效率较高，但是hash表所占空间较多 12  13 3、static final int DEFAULT_INITIAL_CAPACITY = 16; 14  15 4、/** 16  17 　　* The next size value at which to resize (capacity * load factor). 18 　　* @serial 19 　　*/ 20 　　int threshold; 21  22 5、static final int MAXIMUM_CAPACITY = 1 << 30; 23  24 6、static final int DEFAULT_INITIAL_CAPACITY = 16; 25  26 7、final float loadFactor 27  28 决定什么时候进行扩容 29  30 二、方法 31  32 1、核心构造方法 33  34 public HashMap(int initialCapacity, float loadFactor) { 35 if (initialCapacity < 0) 36 throw new IllegalArgumentException("Illegal initial capacity: " + 37 initialCapacity); 38 if (initialCapacity > MAXIMUM_CAPACITY) 39 initialCapacity = MAXIMUM_CAPACITY; 40 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 41 throw new IllegalArgumentException("Illegal load factor: " + 42 loadFactor); 43  44 // Find a power of 2 >= initialCapacity 45 int capacity = 1; 46 while (capacity < initialCapacity) 47 capacity <<= 1; 48  49 this.loadFactor = loadFactor; 50 threshold = (int)(capacity * loadFactor); 51 table = new Entry[capacity];　　//capacity代表数组的长度 52 init(); 53 } 54  55 2、在key对象的hashCodr()方法的基础上再做hash，避免一些不好的hashCode()方法 56  57 //Null keys always map to hash 0,  如果key为null，那么hash()方法的到的hash值为0，再调用indexFor方法得到的数组的索引值也为0，所以key为null的Entry存在数组下标为0的位置 58  59 static int hash(int h) { 60 // This function ensures that hashCodes that differ only by 61 // constant multiples at each bit position have a bounded 62 // number of collisions (approximately 8 at default load factor). 63 h ^= (h >>> 20) ^ (h >>> 12); 64 return h ^ (h >>> 7) ^ (h >>> 4); 65 } 66  67 3、根据2中获得的hash值和数组的长度得到Entry对应的数组的索引 68  69 static int indexFor(int h, int length) { 70 return h & (length-1); 　　//屏蔽高位，保证与操作后最大值为length-1 71 } 72  73 4、根据key获取value 74  75 public V get(Object key) { 76 if (key == null) 77 return getForNullKey();　　//如果key为null则直接取index为0的Entry对应的value值 78 int hash = hash(key.hashCode());　　//生成Entryhash值 79 for (Entry
     
       e = table[indexFor(hash, table.length)];　　//获取header 80 e != null; 81 e = e.next) {　　//链表向下走 82 Object k; 83 if (e.hash == hash && ((k = e.key) == key || key.equals(k)))　　//判断key是否相同 84 return e.value; 85 } 86 return null; 87 } 88  89 5、获取key为null的key对应的值（注意：这里使用在链表中查找的方式，因为index为0的链表上不是只有key为null的Entry） 90  91 private V getForNullKey() { 92 for (Entry
      
        e = table[0]; e != null; e = e.next) { 93 if (e.key == null) 94 return e.value; 95 } 96 return null; 97 } 98  99 6、添加键值对100 101 public V put(K key, V value) {102 103 /*如果key存在则对value进行修改并将原value返回*/104 if (key == null)105 return putForNullKey(value);106 int hash = hash(key.hashCode());107 int i = indexFor(hash, table.length);108 for (Entry
       
         e = table[i]; e != null; e = e.next) {109 Object k;110 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {111 V oldValue = e.value;112 e.value = value;113 e.recordAccess(this);114 return oldValue;115 }116 }117 118 /*如果key不存在则新增键值对*/119 120 modCount++;121 addEntry(hash, key, value, i);122 return null;123 }124 125 7、新增加键值对126 127 void addEntry(int hash, K key, V value, int bucketIndex) {128 Entry
        
          e = table[bucketIndex];　　//获取header129 table[bucketIndex] = new Entry
         
          (hash, key, value, e);　　//new一个新Entry，并将后指针指向原header，新加的Entry成为新header130 if (size++ >= threshold)　　//如果元素个数超过阈值，则进行扩容131 resize(2 * table.length);　　//扩容为原来的2倍132 }133 134 8、扩容135 136 void resize(int newCapacity) {137 Entry[] oldTable = table;138 int oldCapacity = oldTable.length;139 if (oldCapacity == MAXIMUM_CAPACITY) {140 threshold = Integer.MAX_VALUE;141 return;142 }143 144 Entry[] newTable = new Entry[newCapacity];　　//扩容为新capacity145 transfer(newTable);　　//将所有的Entry迁移到新的数组中去146 table = newTable;147 threshold = (int)(newCapacity * loadFactor);　　//重新计算阈值148 }149 150 9、将所有Entry迁移到新数组中151 152 void transfer(Entry[] newTable) {153 Entry[] src = table;154 int newCapacity = newTable.length;155 156 /*遍历Entry数组的0-(size-1)的索引对应的Entry链表，并将链表上的Entry重新计算在新数组中的索引并迁移到新数组的Entry链中*/157 for (int j = 0; j < src.length; j++) {158 Entry
          
            e = src[j];159 if (e != null) {160 src[j] = null;　　//for GC161 do {　　　　//遍历处理某个索引上的Entry链162 Entry
           
             next = e.next;163 int i = indexFor(e.hash, newCapacity);　　//重新计算索引 164 165 /*将所有Entry分别放到应该放到的indexEntry链上*/166 e.next = newTable[i];167 newTable[i] = e;168 e = next;169 } while (e != null);170 }171 }172 }