前注:本文不是讲解Java类库的Hashtable实现原理，而是根据计算机哈希表原理自己实现的一个Hashtable。
HashTable内部是用数组存放一个(Key-Value pair)键值对的引用，其原理是根据Key的hashCode来计算出数组下标。因为存放位置是直接计算出来，不需要遍历数据结构，这使得hash table具有快速增删查改的优势。下面介绍HashTable的实现步骤:
- 取得Key的hashCode。
通过Eclipse等工具可以轻松的复写Object的hashCode方法，生成的hashCode是不会有重复值的。
- 将hashCode与地址映射(压缩地址):
但是，Hashtable内部是用一个数组来存储Key-Value对的，数组容量有限，本文中设置数组容量为10。那么现在的问题就是如何将hashCode和数组地址相对应？一个简单的方法就是对hashCode取模运算(hashCode%10)。这样就可以将hashCode与数组地址做映射（多对一）。同时注意，hashCode可能为负数，而数组的下标不能为负数，所以在映射的时候需要处理一下。
int hashCode = Math.abs(key.hashCode())% this.maxSize;
- 解决hashCode重复问题：
上文已经说过，数组容量为10，当我们在将hashCode映射为数组下标的时候，肯定会遇到有重复的情况。比如hashCode为21和31，分别对他们取模运算，结果都是1，也就是说这两个hashCode对应数组的下标都是1.那么第一个元素添加上去后，再添加第二个元素，则新元素会覆盖之前的元素。这时，如果我们想后面添加的重复地址元素也能添加上去，只能将其放在其它位置。这时，我们可以将新元素放在改地址的下一位，如果下一位已经有元素，那么就继续往后找，直到找到空位为止（其实这个过程有些边界条件需要考虑，比如找到数组末尾后应跳到数组开头继续找。以及数组已经满了，找遍数组都找不到合适的位置，就应该提示该数组已满，不能插入）。
现在既然解决了上面的问题，也就是说每个元素都能在数组中找到合适的位置（除非数组已满）。那么可以根据这个算法实现数组的增删查改。下面是Hashtable的实现代码:
package org.lyk.impl; public class HashTable<K, V>
{
/**
* Key-Value pair 存放键值对
* @author liuyuank
*
*/
private class KeyValue
{
K key;
V value; private KeyValue(K key, V value)
{
this.key = key;
this.value = value;
} public K getKey()
{
return key;
} public void setKey(K key)
{
this.key = key;
} public V getValue()
{
return value;
} public void setValue(V value)
{
this.value = value;
} } private Object[] table;
private int maxSize = 10;
private int currentAmmount = 0; public HashTable()
{
this.table = new Object[this.maxSize];
} public HashTable(int maxSize) throws Exception
{
if (0 == maxSize || maxSize < 0 || maxSize > 100)
{
throw new Exception("table容量非法!");
} this.maxSize = maxSize;
this.table = new Info[maxSize];
} /**
* 增加一个键值对
* @param key
* @param value
*/
public void add(K key, V value)
{
//将hashCode映射到数组下标
int hashCode = Math.abs(key.hashCode())% this.maxSize; //将元素插入到数组中，如果该位置已经被占用，则循环查找下一个位置，直到找到合适的位置，或发现数组已满，退出循环
while (this.table[hashCode] != null
&& (this.currentAmmount < this.maxSize))
{
hashCode++;
hashCode = hashCode % this.maxSize;
} if (this.currentAmmount == this.maxSize)
{
//数组已满
System.out.println("Hash table 已满");
} else
{
//找到合适位置
this.table[hashCode] = new KeyValue(key, value);
this.currentAmmount++;
}
} /**
* 与add方法同样的算法，根据key值找到数组中元素，然后将改元素设置为null
* @param key
* @return
*/
public boolean remove(K key)
{
int hashCode = Math.abs(key.hashCode()) % this.maxSize;
int count = 0;
while (this.table[hashCode] != null && count < this.maxSize)
{
if (((KeyValue) this.table[hashCode]).getKey().equals(key))
{
this.table[hashCode] = null;
return true;
}
count++;
hashCode++;
hashCode = hashCode%this.maxSize;
} return false;
} public V get(K key)
{
int hashCode = Math.abs(key.hashCode()) % this.maxSize;
int count = 0;
while (this.table[hashCode] != null && count < this.maxSize)
{
if (key.equals(((KeyValue)this.table[hashCode]).getKey()))
return ((KeyValue) this.table[hashCode]).getValue(); hashCode++;
count++;
hashCode = hashCode%this.maxSize;
}
return null;
} public boolean contains(K key)
{
if (this.get(key) != null)
{
return true;
} else
{
return false;
}
} public void replace(K key, V value)
{
KeyValue kv = this.find(key);
if(kv != null)
{
kv.setValue(value);
}
} private KeyValue find(K key)
{
int hashCode = Math.abs(key.hashCode()) % this.maxSize;
int count = 0;
while (this.table[hashCode] != null && count < this.maxSize)
{
if (key.equals(((KeyValue)this.table[hashCode]).getKey()))
return ((KeyValue) this.table[hashCode]); hashCode++;
count++;
hashCode = hashCode%this.maxSize;
}
return null;
}
}
HashTable实现
package org.lyk.impl; import java.math.BigInteger; public class Info
{
private String name;
private String address;
private Integer age; public Info(String name, String address, Integer age)
{
super();
this.name = name;
this.address = address;
this.age = age;
}
@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + ((address == null) ? 0 : address.hashCode());
result = prime * result + ((age == null) ? 0 : age.hashCode());
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
} // @Override
// public int hashCode()
// {
// final int prime = 27;
// int result = 1;
// result = prime*result + (this.name == null ? 0:this.name.hashCode());
// result = prime*result + (this.address == null ? 0:this.address.hashCode());
// result = prime*result + (this.age == null ? 0 : this.age.hashCode());
// return result;
// } @Override
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Info other = (Info) obj;
if (address == null)
{
if (other.address != null)
return false;
} else if (!address.equals(other.address))
return false;
if (age == null)
{
if (other.age != null)
return false;
} else if (!age.equals(other.age))
return false;
if (name == null)
{
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
public String getName()
{
return name;
}
public void setName(String name)
{
this.name = name;
}
public String getAddress()
{
return address;
}
public void setAddress(String address)
{
this.address = address;
}
public Integer getAge()
{
return age;
}
public void setAge(Integer age)
{
this.age = age;
}
@Override
public String toString()
{
return "Info [name=" + name + ", address=" + address + ", age=" + age
+ "]";
} }
Value实现
测试代码:String为Key Info为Value
package org.lyk.main; import org.lyk.impl.BiTree;
import org.lyk.impl.HashTable;
import org.lyk.impl.Info; public class Main
{
public static void main(String[] args)
{
HashTable<String, Info> ht = new HashTable<>();
for(int i =0; i <15;i++)
{
Info info = new Info("sheldon" + i, "address" + i , i);
//System.out.println("hashCode in main:" + info.getName().hashCode());
ht.add(info.getName(), info);
} String key = "sheldon3";
System.out.println(ht.contains(key));
ht.replace(key, new Info("谢耳朵","美国洛杉矶", 999));
System.out.println(ht.contains(key));
System.out.println(ht.get(key));
System.out.println("///~ main done");
} }