HashMap学习笔记1
先说说HashMap的几个特点：
1、无序的（那它的存取速度咋还那么快呢？）
2、线程不安全的（存取不同步）
第二个特点没撒好说的，我们主要说说第一个；首先我们先看一下HashMap的结构图：
由上图我们可以看出，它是一个数组加列表的混合结构（横行数组，纵向链表）。结合结构图和源码我们一起来看看HashMap的put和get的原理：
a、put源码
public V put(K key, V value) {
if (key == null)
return putForNullKey(value); //null总是放在数组的第一个链表中
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);//数组对应的位置
//遍历链表
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
//如果key在链表中已存在，则替换为新value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e); //参数e, 是Entry.next
//如果size超过threshold，则扩充table大小。再散列
if (size++ >= threshold)
resize(2 * table.length);
}
由源码可以看出put操作分为以下几步：
1、对key值进行hash编码，得到对应的数组位置
2、取出对应位置的链表，如果链表为空，则直接插入；否则遍历链表，存在相同key，就覆盖，不存在就在链表末尾插入
对于这个两点是不是觉得有点抽象，不是很好懂，缺点什么？我们来说点人话，为什么要做上述操作呢？有个专业名词叫散列冲突拉链法，HashMap的初始化数组大小是16，在对大量数据操作hashcode很容易产生碰撞冲突，为了解决冲突就加上了链表结构。
b、get源码
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
//先定位到数组元素，再遍历该元素处的链表
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
有了上面put的讲解之后，是不是觉得get就很容易理解了！还是简单写一下，它和put一样也是分为两步：
1、对key值进行hash编码，得到对应的数组位置
2、取出对应位置的链表，遍历链表找出key值对应的值
分解完HashMap的存取机制之后，我们来看看它的两种遍历方式：
第一种
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
效率高,以后一定要使用此种方式！
第二种
Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}
效率低,以后尽量少使用！
骚年们按耐不住了吧，一定想问为什么吧？满足你，一切都在源码中：
private final class KeyIterator extends HashIterator {
public K next() {
return nextEntry().getKey();
}
}
private final class EntryIterator extends HashIterator> {
public Map.Entry next() {
return nextEntry();
}
}
从源码中我们可以看出
方法一：keySet只是将HashMap中所有的key值进行了iterator，然后根据key值重新去map中取值（相信看了前面的讲解，你一定明白这个重新是很耗时的）
方法二：entryset只遍历了1次，就把key和value都放到了entry中，所以就快了。
意犹未尽？再来点什么？好满足你：
从存取机制中我们看出来，所有的key值都要进行一次hash编码操作，再去定位存放位置的，所以你选定的key值对你的存取速度影响是非常大的。理论上Integer的速度应该是最快的，因为它的hash编码就是它本身，当然使用最多的String速度也还好，你非要逆天的整一些奇葩的object对象，那我也就无话可说了！
