HashSet、HashMap，散列表数据结构（哈希表） (三)

// get方法源码
[java]
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode()); // 还是计算key的hashcode，
// 定位hash值在table数组中的索引,并通过equals方法定位元素在链表中的位置。
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;
}

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode()); // 还是计算key的hashcode，
// 定位hash值在table数组中的索引,并通过equals方法定位元素在链表中的位置。
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;
}
我们来对HashMap存取元素的过程来做一个小的总结：

元素(key,value)在HashMap中被封装进Entry数组。
put元素的时候，根据key的hash值定位元素在Entry数组中的索引，如果当前索引有元素，就通过equals方法进行比较，将元素存进当前Entry的链表中适当的位置。
get元素的时候，根据key的hash值定位元素在Entry数组中的索引，然后通过equals方法定位元素在链表中的位置，取出该元素。

性能分析：

因为元素的存取是通过hash算法进行的，所以速度都没的说。
在查找操作中，唯一影响性能的是在链表中，但实际只要优化好了key对象hashCode跟equals方法，就会避免链表中的数据过多而导致查找性能变慢。

再一个非常影响性能的是数组扩容操作，当使用默认的DEFAULT_INITIAL_CAPACITY对HashMap进行初始化的时候，
如果元素个数非常多，会导致扩容次数增加，每次扩容都会进行元素位置的重新分配，这是相当耗费性能的。
如果能预算好元素个数，就应该避免使用默认的DEFAULT_INITIAL_CAPACITY，可在HashMap的构造函数中为其指定一个初始值。

问题解决：

hashCode必须和equals保持兼容(equals方法的判断依据和计算hashCode的依据相同)，这样做是为了避免链表中的数据过多。

举例：
[java]
public class Person {
public int id;
public String name="";

public int hashCode() {
return id;
}
// equals必须比较id
public boolean equals(Person p) {
if(this.id == p.id)
return true;
else
return false;
}
}

public class Person {
public int id;
public String name="";

public int hashCode() {
return id;
}
// equals必须比较id
public boolean equals(Person p) {
if(this.id == p.id)
return true;
else
return false;
}
}
如果元素很多，应该使用这个构造函数public HashMap(int initialCapacity){}对HashMap进行初始化。
举例：HashMap map = new HashMap(1024);

了解了HashMap的存储原理之后，自然也就明白了为什么说HashSet的存取效率高了。