【数据结构】Linux中散列存储结构 --- 哈希表

哈希表：

   即散列存储结构。

散列法存储的基本思想：
   建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。

链地址法(拉链法）处理冲突：
   基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

实现：

class Node<T>
{
	public int key;
	public T value;
	public Node<T> next;
	public Node(int key,T value)
	{
		this.key=key;
		this.value=value;
		this.next=null;
	}
}

public class MyHash<T>
{
	private Node<T>[] buckets;
	private Node node;
	
	public MyHash()
	{
		this.buckets=(Node<T>[])new Object[10]; 
	}
	public MyHash(int size)
	{
		this.buckets=(Node<T>[])new Object[size]; 
	}
	//覆盖相同key
	public boolean replaceAttribute(int key, T value)
	{
		int index=key%this.buckets.length;   //确认数组索引位置
		Node<T> p=this.buckets[index];    //获得头指针
		while(p!=null)
		{
		   if(p.key==key) break;    //key重复
		   p=p.next;
		}
		if(p!=null){  p.value=value; return true;} //相同key，就进行覆盖
		return false;
	}
	//加入节点
	public boolean addAttribute(int key, T value)
	{
		int index=key%this.buckets.length;
		Node<T> p=this.buckets[index];      //获得头指针
		while(p!=null)
		{
		   if(p.key==key) break;    //key重复
		   p=p.next;
		}
		if(p!=null) return false;    //由break退出循环，则key重复，加入失败
		p=new Node<T>(key,value);
	    p.next=this.buckets[index];  //头插法插入节点
	    this.buckets[index]=p;
	    return true;
	}
	//获得关键字对应值
	public T  getAttribute(int key)
	{
		int index=key%this.buckets.length;
		Node<T> p=this.buckets[index];  //获得头指针
		Node<T> q=null;
		while(p!=null)
		{
		   if(p.key==key) break;   //得到key对应的节点p
		   q=p;
		   p=p.next;
		}
		if(p==null) return null;    //key不在表中，搜索失败
		if(p==this.buckets[index])  //p为头指针，删除p后则下一节点为头节点
			this.buckets[index]=p.next;
		else
		{
			q.next=p.next;     //将p删除
		}
		return p.value;
	}
	
}