一．哈希表的相关概念
哈希函数的构造方法：
1. 直接定址法
2. 数字分析法
3. 平法取中法
4. 折叠法
5. 除留余数法
6. 随机数法
二．处理冲突的方法
1. 开放定制法（线性探测再散列、二次探测再散列、伪随机探测再散列）
2. 再哈希法
3. 链地址法
4. 建立一个公共溢出区
三．MyHashMap的实现
要点：哈希函数的方法选用“除留余数法”，处理冲突的方法是用“链地址法”，也即是当发生冲突时，凡是哈希地址为i的记录，都插入到头指针为tables[i]的链表中，插入的位置可以是表头，也可以是表尾，也可以在中间（以保持key的有序）。
本次实现的MyHashMap是将其插入表头。
package edu.njupt.zhb;
/*
*@author: ZhengHaibo
*web: http://blog.csdn.net/nuptboyzhb
*mail: zhb931706659@126.com
*2014-3-25 Nanjing,njupt,China
*/
public class MyHashMap<K,V>{
/**
* HashMap数组中的节点
* @param <K>
* @param <V>
*/
public class MyEntry<K,V>{
public K key;//键
public V value;//值
public MyEntry<K,V> next;//下一个结点
}
private MyEntry<K, V> []tables;
private final int INIT_LEN=50;
public MyHashMap() {
tables=new MyEntry[INIT_LEN];
}
/**
* 哈希函数的构造方法：除留余数法
* @param hashcode
* @return
*/
public int indexFor(int hashcode){
return Math.abs(hashcode)%tables.length;
}
/**
* 获取键为key的值
* @param key
* @return
*/
public V get(K key){
if(key==null){
return null;
}
int hashcode=key.hashCode();//计算键的哈希值
int index=indexFor(hashcode);//根据哈希值计算其在表中的下标index
MyEntry<K, V> pNode=tables[index];//取出第一个节点，也即是链表的头
//在链表中查找
while(pNode!=null){//对链表进行遍历
//当key的哈希值和真实值相等时返回
if(pNode.key.hashCode()==hashcode&&(key==pNode.key || key.equals(pNode.key))){
return pNode.value;
}
pNode=pNode.next;//链表：遍历下一个值
}
return null;
}
/**
* 将键值对放入map当中
* 解决冲突的方法：链地址法
* @param key
* @param value
* @return
*/
public V put(K key,V value){
if(key==null){
return null;
}
int hashcode=key.hashCode();
int index=indexFor(hashcode);
MyEntry<K, V> head=tables[index];//取出第一个节点，也即是链表的头
MyEntry<K, V> pNode=head;
//首先查找是否已经存在key
while(pNode!=null){
//当key的哈希值和真实值相等时
if(pNode.key.hashCode()==hashcode&&(key==pNode.key || key.equals(pNode.key))){
pNode.value=value;//更新当前key的值
return pNode.value;
}
pNode=pNode.next;//链表：遍历下一个值
}
//如果没有查找到，将该值插入到链表的表头
MyEntry<K, V> newNode=new MyEntry<K,V>();
newNode.key=key;
newNode.value=value;
newNode.next=head;
tables[index]=newNode;
return value;
}
/**
* 根据key删除对应的值
* 思路：先查找，后删除
* @param key
* @return
*/
public V remove(K key){
if(key==null){
return null;
}
int hashcode=key.hashCode();
int index=indexFor(hashcode);
MyEntry<K, V> head=tables[index];
MyEntry<K, V> pNode=head;
if(pNode==null){
return null;
}
//表头
if(pNode.key.hashCode()==hashcode&&(key==pNode.key || key.equals(pNode.key))){
V value=pNode.value;
tables[index]=pNode.next;//删除头节点
return value;
}
//首先查找是否已经存在key
while(pNode.next!=null){
//当key的哈希值和真实值相等时
if(pNode.next.key.hashCode()==hashcode&&(key==pNode.next.key || key.equals(pNode.next.key))){
V value=pNode.value;
pNode.next=pNode.next.next;//删除该节点
return value;
}
pNode=pNode.next;//链表：遍历下一个值
}
return null;
}
public void print(){
for(int i=0;i<tables.length;i++){
MyEntry<K, V> entry=tables[i];
if(entry!=null){
while(entry!=null){
System.out.println("key="+entry.key+",value="+entry.value);
entry=entry.next;
}
}
}
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
MyHashMap<String, String> map=new MyHashMap<String, String>();
for(int i=0;i<100;i++){
map.put("stu"+i, ""+i);
}
for(int i=0;i<20;i++){
map.remove("stu"+i);
}
map.print();
}
}
四.MyHashSet的实现
思路：和HashMap的思路一样，我们也是先计算hash值,然后折算出位置index，然后进行插入或删除。查找元素的效率很高，不需要对所有元素进行比较。
package edu.njupt.zhb;
/*
*@author: ZhengHaibo
*web: http://blog.csdn.net/nuptboyzhb
*mail: zhb931706659@126.com
*2014-3-25 Nanjing,njupt,China
*/
public class MyHashSet<T>{
/**
* 节点
*/
public class MyEntry<T>{
public T data;//当前数据
public MyEntry<T> next;
}
private MyEntry<T> []tables;//数组
private final int INIT_LEN=50;
private int size;
public MyHashSet(){
tables=new MyEntry[INIT_LEN];
size=0;
}
/**
* 哈希函数构造方法
* @param hashcode 哈希值
* @return 对应的数组下标
*/
private int indexFor(int hashcode){
return Math.abs(hashcode)%tables.length;
}
/**
* 添加元素
* @param object
* @return
*/
public boolean add(T data){
if(data==null){
return false;
}
int hashcode=data.hashCode();//计算哈希值
int index=indexFor(hashcode);//定位存储的位置
MyEntry<T> head=tables[index];//取出该位置的第一个元素（链表的头）
MyEntry<T> pNode=head;//查找链表中是否存在
while(pNode!=null){
if(pNode.data.hashCode()==hashcode&&(pNode.data==data||pNode.data.equals(data))){
return false;//已经存在重复的元素
}
pNode=pNode.next;
}
//不存在重复的元素或该位置为空,将该节点添加到链表的头
MyEntry<T> newNode=new MyEntry<T>();
newNode.data=data;
newNode.next=head;
tables[index]=newNode;
size++;
return true;
}
public boolean remove(T data){
if(data==null){
return false;
}
int hashcode=data.hashCode();
int index=indexFor(hashcode);
MyEntry<T> head=tables[index];
MyEntry<T> pNode=head;
if(pNode.data.hashCode()==hashcode&&(pNode.data==data||pNode.data.equals(data))){
tables[index]=pNode.next;
size--;
return true;
}
while(pNode.next!=null){
if(pNode.next.data.hashCode()==hashcode&&(pNode.next.data==data||pNode.next.data.equals(data))){
pNode.next=pNode.next.next;//删除该元素
size--;
return true;
}
pNode=pNode.next;
}
return false;
}
public void print(){
for(int i=0;i<tables.length;i++){
MyEntry<T> entry=tables[i];
if(entry!=null){
while(entry!=null){
System.out.println(entry.data);
entry=entry.next;
}
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MyHashSet<String> set=new MyHashSet<String>();
for(int i=0;i<100;i++){
set.add(i+"");
}
for(int i=0;i<10;i++){
set.remove(i+"");
}
System.out.println(set.size);
set.print();
}
}
附录：
用链地址法处理冲突时的Hash表结构示意图如下：
相关博客:
[1].HashMap的实现原理：http://zhangshixi.iteye.com/blog/672697
[2].LinkedHashMap的实现原理： http://zhangshixi.iteye.com/blog/673789