Java HashMap
标签（空格分隔）： Java source-code hash-map
总结
- HashTable的基本数据结构
- Entry的hash与table的长度计算indexFor才能算出entry在table中的链表头节点位置
- HashMap中比较key是否相同的算法 e.hash == hash && ((k = e.key) == key || key.equals(k))
- == 与 equal
- hashMap的遍历方式，hashMap本身没有实现Iterator，提供了三个set，entrySet keySet vaulues，三者都是基于HashIterator，都是获取entry进行数据访问的。
HashMap 的数据结构模型
Paste_Image.png
table: Entry[]，Entry的数组，table[i]里存着hash(key)对应着某个hash值的链表的头指针。
Entry:范型数据结构，就是一个链表的节点，key，value，next（指向下一个节点），hash
放入Put
加入一个key-value键值对，即要加入一个entry。首先计算entry的hash，计算该hash应该存在table中的那个链表中（index(hash,table.length)) ，从头节点开始寻找
- 若已经有存在的 key，则替换将该entry的value更新，返回oldvalue
- 若为新的key，构建新的entry，加入此hash对应的链表中
查看key的比较
Java 示例：
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;
}
}
所以说Key为自定义的类时，要注意==与equals方法。
equals 与 ==
1.基本数据类型，也称原始数据类型。
byte,short,char,int,long,float,double,boolean
他们之间的比较，应用双等号（==）,比较的是他们的值。
2.复合数据类型(类)
当他们用（==）进行比较的时候，比较的是他们在内存中的存放地址，所以，除非是同一个new出来的对象，他们的比较后的结果为true，否则比较后结果为false。
JAVA当中所有的类都是继承于Object这个基类的，在Object中的基类中定义了一个equals的方法，这个方法的初始行为是比较对象的内存地 址，但在一些类库当中这个方法被覆盖掉了，如String,Integer,Date在这些类当中equals有其自身的实现，而不再是比较类在堆内存中的存放地址了。
对于复合数据类型之间进行equals比较，在没有覆写equals方法的情况下，他们之间的比较还是基于他们在内存中的放位置的地址值的，因为Object的equals方法也是用双等号（==）进行比较的，所以比较后的结果跟双等号（==）的结果相同。
HashMap中存入的是新的值是，会
addEntry(hash, key, value, i);
return null;
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
resize之后，要进行旧表到新表的transfer，注意两点，
1 旧的一条链表保存的是按照原来hash值计算出来的index(hash, table.length)一致，换成新表后，链表结构要改变，并不是单纯的把链表挪位置。想想，要是单纯的把链表在table上进行挪位子，resize也就没有意义了，resize就是为了减少hash冲突的。
2 transfer函数可以认真看下
transfer函数
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
HashSet
HashSet实现基于HashMap,key比较出来相等时候，会进行覆盖，因而保持了Set中相同的元素只出现一次。
private transient HashMap<E,Object> map;
