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 阅读(690)
评论(0) 编辑 收藏 所属分类:
J2SE