1、構造方法：HashMap<K, V>有4個構造方法：
1.1、用指定初始容量和指定加載因子構造一個新的空哈希表。
1 /**
2 * Constructs an empty <tt>HashMap</tt> 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
20 // Find a power of 2 >= initialCapacity
21 int capacity = 1;
22 while (capacity < initialCapacity)
23 capacity <<= 1;
24
25 this.loadFactor = loadFactor;
26 threshold = (int)(capacity * loadFactor);
27 table = new Entry[capacity];
28 init();
29 }
可以看出HashMap1)無容量限制，但是其Entry[] table是有長度限制的，最大長度為2^30；2)Entry[] table的長度始終為2的指數冪。
Map<String, String> map = new HashMap(5, 0.64f)
來創建一個map對象，則可以看出map的容量為8，而不是5；在該map的容量大于0.64*8時候，開始擴容。擴容方式在后面講。這里的init()方法在JDK_1.6.0_16中是一個空方法。
1.2、public HashMap(int initialCapacity)同
HashMap(initialCapacity, 0.75f);
1.3、public HashMap()
HashMap(16, 0.75f);
1.4、構造一個指定Map具有相同關系映射關系的新HashMap<K, V>
1 public HashMap(Map<? extends K, ? extends V> m) {
2 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
3 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
4 putAllForCreate(m);
5 }
2、put(K key， V value)
2.1、key == null則
取table[0]并對table[0].next進行遍歷，如果找到為null的key把value替換，并將原來的value返回；
如果沒有找到則在Entry<K, V> e = table[0];table[0] = new Entry(0, null, value, e);
其中Entry的參數意義分別為：hash(key.hashCode())；key；value；Entry<K, V>
2.2、key != null則
1）計算key的hash；hash = hash(key.hashCode())；
2）找到該key位于Entry<K, V>table的下標index
3）取Entry<K,V> e = table[index]；對e.next進行遍歷查找key，查找方式為：
(Object k = e.key) == key || (key != null && key.equals(k);
3.1）找到，則把value替換；并將原來的value返回。
3.2）沒有找到，Entry<K, V> e = table[hash];table[hash] = new Entry<K,V>(hash, key, value, e)
可以看出，如果有相同的hash，HashMap的存儲方式為：鏈表存儲的。
3、get(Object key)
和put<K k, V v>的查找方式一樣。
4、remove(Object key)
也是先計算hash，然后找到table的下標，對該下標的Entry<K, V>.next進行遍歷；查找方式為：
e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))
找到則把table[index] = table[index].next;
5、計算hash的處理。hash(int h)JDK上的解釋是為了盡可能的避免key的hashCode的沖突，
但是為什么要這么計算hash目前看不懂
1 static int hash(int h) {
2 // This function ensures that hashCodes that differ only by
3 // constant multiples at each bit position have a bounded
4 // number of collisions (approximately 8 at default load factor).
5 h ^= (h >>> 20) ^ (h >>> 12);
6 return h ^ (h >>> 7) ^ (h >>> 4);
7 }
6、查找下標的操作：indexFor(int h, int length)
Sun JDK采取位運算，而不是采用整除，這樣效率高
static int indexFor(int h, int length) {
return h & (length-1);
}
PS：HashSet是基于HashMap實現的，HashSet.add(k)相當于HashMap.put(k, new Object());
posted on 2011-08-16 00:24
showsun 閱讀(706)
評論(0) 編輯 收藏 所屬分類:
J2SE