对于HashMap感觉一直是看了忘，忘了看。这里就单独写一篇日志来记录一下。HashMap的底层实现。
非常好的讲HashMap的博客：http://blog.csdn.net/vking_wang/article/details/14166593
我们看一下HashMap的底层结构：
我们看到底层是一个数组,数组里面存放的是Entry,Enrty是什么？
我们看一下源代码：
//很明显这是一个单向链表，next是只想下一个Entry的
//Key就是我们键值
//value是我们的值
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash; /**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
} public final K getKey() {
return key;
} public final V getValue() {
return value;
} public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
} public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
} public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
} public final String toString() {
return getKey() + "=" + getValue();
} /**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
} /**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
这个就是数组里面存放的Entry,里面存放了Key键值还有键值对应的value。
我们思考的问题是，HashMap是怎么把key和value放进去的，我们常用的就是：
HashMap hashmap=new HashMap();
hashmap.put(key,value);
其实就是根据传进来的key的值计算hash值，根据hash值确定要放在数组的哪个位置。比如放在table[2];
先去table[2]这个位置找Entry,Entry是一个链表，遍历这个链表，发现这个链表中有key的值相等与传进来的key相等那么之前的值就被替换掉，并且把老的值返回。
对应的源代码是：
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
但是如果我们在table[2]这个位置看到本身就没有Entry的话，我们就要新增一个Entry。
代码如下：
我们看一下addEntry的代码：
void addEntry(int hash, K key, V value, int bucketIndex) {
//把table数组上面的Entry取出来，
Entry<K,V> e = table[bucketIndex];
//新建一个Entry,并把之前取出来的Entry挂在到这个新加入的Entry的next
//下面
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
我们再看一下HashMap是怎么取值的：
hashmap.get(Key):
代码如下：
先找到Table数组里面Entry的位置，然后从这个位置里面搜索这个Entry这个单链表，找到key对应的Entry的value。
上面三种遍历方法，给出一个例子来讲解：
import java.util.Map;
import java.util.Random;
import java.util.Iterator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Collection; /*
* @desc 遍历HashMap的测试程序。
* (01) 通过entrySet()去遍历key、value，参考实现函数：
* iteratorHashMapByEntryset()
* (02) 通过keySet()去遍历key、value，参考实现函数：
* iteratorHashMapByKeyset()
* (03) 通过values()去遍历value，参考实现函数：
* iteratorHashMapJustValues()
*
* @author skywang
*/
public class HashMapIteratorTest { public static void main(String[] args) {
int val = 0;
String key = null;
Integer value = null;
Random r = new Random();
HashMap map = new HashMap(); for (int i=0; i<12; i++) {
// 随机获取一个[0,100)之间的数字
val = r.nextInt(100); key = String.valueOf(val);
value = r.nextInt(5);
// 添加到HashMap中
map.put(key, value);
System.out.println(" key:"+key+" value:"+value);
}
// 通过entrySet()遍历HashMap的key-value
iteratorHashMapByEntryset(map) ; // 通过keySet()遍历HashMap的key-value
iteratorHashMapByKeyset(map) ; // 单单遍历HashMap的value
iteratorHashMapJustValues(map);
} /*
* 通过entry set遍历HashMap
* 效率高!
*/
private static void iteratorHashMapByEntryset(HashMap map) {
if (map == null)
return ; System.out.println("\niterator HashMap By entryset");
String key = null;
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next(); key = (String)entry.getKey();
integ = (Integer)entry.getValue();
System.out.println(key+" -- "+integ.intValue());
}
} /*
* 通过keyset来遍历HashMap
* 效率低!
*/
private static void iteratorHashMapByKeyset(HashMap map) {
if (map == null)
return ; System.out.println("\niterator HashMap By keyset");
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
key = (String)iter.next();
integ = (Integer)map.get(key);
System.out.println(key+" -- "+integ.intValue());
}
} /*
* 遍历HashMap的values
*/
private static void iteratorHashMapJustValues(HashMap map) {
if (map == null)
return ; Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}
}
下面的一篇博客我们就要讲解TreeMap了，TreeMap涉及到红黑树，看完代码面试那本书的二叉树那个章节在来看这方面的内容。