前面说到，存入HashMap、HashSet的元素必须定义equals()方法和HashCode()方法，默认的HashCode()方法是Object的方法，其生成的散列码是使用对象的地址计算散列码，所以你new出来的两个类是具有不同的散列码的，尽管我们有时候希望当两个对象具有向相同的属性的时候，那么认为它们是同一个对象，这个时候就需要根据自己的需求重写HashCode()方法了，同时你还应该覆盖equals()方法，equals()方法会判断这个元素是否存在容器中，在前面有说到，而默认的equals()方法也是比较的元素的地址，我们可以按照自己的需求覆盖equals()方法。
正确的equals()方法必须满足下列5个条件：
1.自反性。对任意的x, x.equals(x) 一定返回true；
2.对称性。对任意的x和y, 如果x.equals(y)返回true, 则y.equals(x)一定返回true;
3.传递性。对任意x、y、z, 如果有x.equals(y)返回true, y.equals(z) 返回true，则x.equals(z)一定返回true;
4.一致性。对任意x和y，如果对象中用于等价比较的信息没有改变，那么无论调用x.equals(y)多少次，返回的结果应该保持一致，要么一直是true，要么一直是false。
5.对任何不适null的x，x.equals(null)一定返回false。
为速度而散列
散列的价值在于速度：散列使得查询得以快速进行。散列将键保存在某处，以便能快速找到。存储一组元素最快的数据结构是数组，所以使用数组来表示键的信息（注意是信息而不是本身），数组并不保存键本身，而是同过键对象生成一个数字，将其作为数组的下标。这个数字就是散列码。
由于数组的容量是固定的，而容器的容量是不固定的，所以不能将Map的键直接存在数组里面，Map里面用来存储键的信息的是一个容量固定的数组，该数组装的是一个list，map通过计算对象的hashCode值，将hashCode值对该数组的size去余，然后将该余数作为数组的下标，将该对象作为键值放入数组下标位置的list里面，所以不同的键可能产生相同的下标，也就是可能产生冲突，当产生冲突时，将该键使用equals() 方法去与该键产生的下标的位置的list中的元素去比较，如果散列函数好的话，数组的每个位置的list只有较少的值，因此不是查询整个容器的元素，而是很快跳到数组的某个位置对很少的元素进行比较，这便是HashMap会如此快的原因。理解了散列的原理，就可以实现一个以下的简易的散列的Map了：
上代码：
public class SimpleHashMap<K, V> extends AbstractMap<K, V>{
private static final int SIZE = 997;
LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
@Override
public V put(K key, V value) {
V oldValue = null;
//对hashCode取余
int index = Math.abs(key.hashCode()) % SIZE;
if(buckets[index] == null){
buckets[index] = new LinkedList<MapEntry<K, V>>();
}
LinkedList<MapEntry<K,V>> bucket = buckets[index];
//标识符检查容器类是否有该键
boolean found = false;
ListIterator<MapEntry<K, V>> listIterator = bucket.listIterator();
while(listIterator.hasNext()){
MapEntry<K, V> mp = listIterator.next();
if (mp.getKey().equals(key)){
//该键存在，先将该键之前的值存起来，然后替换成要设置成的值，最后将标识符改成true表示该键存在
oldValue = mp.getValue();
listIterator.set(mp);
found = true;
break;
}
}
//如果容器中这个键不存在
if (!found){
buckets[index].add(new MapEntry<K, V>(key, value));
}
return oldValue;
}
@Override
public V get(Object key) {
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets[index] == null) return null;
LinkedList<MapEntry<K,V>> linkedList = buckets[index];
ListIterator<MapEntry<K, V>> iterator = linkedList.listIterator();
while(iterator.hasNext()){
MapEntry<K, V> mapEntry = iterator.next();
//若果找到key
if (mapEntry.getKey().equals(key)){
return mapEntry.getValue();
}
}
return null;
}
@Override
public Set<Entry<K, V>> entrySet() {
Set<Map.Entry<K,V>> set = new HashSet<Entry<K, V>>();
for (LinkedList<MapEntry<K, V>> bucket : buckets) {
if (bucket == null) continue;
for (MapEntry<K, V> mapEntry : bucket) {
set.add(mapEntry);
}
}
return set;
}
public static void main(String[] args) {
SimpleHashMap<String, String> m = new SimpleHashMap<String, String>();
m.put("key1","value1");
m.put("key2","value2");
m.put("key3","value3");
System.out.println(m);
System.out.println(m.get("key2"));
System.out.println(m.entrySet());
}
}
MapEntry是一个自己写的十分简单的类，该类实现了Map.Entry接口，可以保存和读取键与值，它的entrySet()用来产生键值对的Set.
/**
MapEntry.java
*/
public class MapEntry<K, V> implements Map.Entry<K, V> {
private K key;
private V value;
public MapEntry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V value) {
V result = this.value;
this.value = value;
return result;
}
@Override
public int hashCode() {
return (key ==null ? 0 : key.hashCode())^(value == null ? 0 : value.hashCode());
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof MapEntry)){
return false;
}
MapEntry me = (MapEntry) obj;
return (key == null ? me.getKey() == null : key.equals(me.getKey())) &&
(value == null ? me.getValue() == null : value.equals(me.getValue()));
}
@Override
public String toString() {
return key + "=" + value;
}
}
