对哈希表的一些理解

哈希表浅谈

  哈希表通俗来说是将数据以某种规则计算来取到一个关键值key，然后查找时直接通过关键值key直接找到数据，这样平均情况下时间复杂度为O(1)。但是因为规则并不是万能的，所以会使得不同的数据得出的关键值一样，产生冲突。解决冲突的方法有两种，一个方法是为冲突关键字在哈希表中寻找另一个位置，称开放寻址法，一个方法是把在相同位置的所有关键字都存储在一个“挂”在那个位置上的数据结构中，称封闭寻址法。
  以我自己做过的例子来说，比较熟悉第二个方法中采用挂链法。具体实现方法是结合数组和链表，相当于创建一个链表数组，之后根据数据情况来设置规则，求出对应的关键值，然后进行存储。如果有两个或多个数据冲突的话，就将第一个放进那个单元的数据作为头结点，其余冲突的数据则依次往下，变成在链表中存储。但是如果冲突很多，那么必定会影响查找效率，这样就要进行rehash操作，那什么时候进行rehash操作，以及怎样rehash。确认这个时间点可以通过设置一个负载因子来解决，比如你的哈希表数组长度是m,但是你已经存储了n个数据，而n/m就为负载因子。从负载因子的大小中判断存储的数据是否有很多都冲突了，如果负载因子过大，就需要rehash。
之后是代码的编写：
package 哈希表0412;
import java.util.LinkedList;
public class myHashTable {
private int length=100;
private LinkedList<Student> array[]=new LinkedList[length];
private int count;
private int threshold=(array.length)*2;

//求取关键值key
private int getKey(String id){
int sum=id.hashCode();
int index=(sum)%(array.length);
return index;

}

//添加数据
public void add(Student st){
if(st.getId()==null){
throw new NullPointerException();
}
int index=getKey(st.getId());
if(array[index]==null){
LinkedList<Student> ll=new LinkedList<Student>();
ll.add(st);
array[index]=ll;
}else{
array[index].add(st);
}
if((count++)>=threshold){
rehash(2*array.length);
}
}
//查找数据
public Student get(String id){
int index=getKey(id);
//遍历链表
for(int i=0;i<array[index].size();i++){
if(array[index].element().getId()==id){
Student st=array[index].element();
// System.out.println(st);
return st;

}
}
return null;

}
//删除数据
public void remove(String id){
int index=getKey(id);
for(int i=0;i<array[index].size();i++){
if(array[index].element().getId()==id){
Student st=array[index].remove();
// System.out.println(st.getCourse());
}
}
}
public void rehash(int length){
count=0;
LinkedList<Student> arrayOther[]=new LinkedList[length];
}
}
以上代码中的rehash中，只是扩容了哈希表数组的范围，但我觉得只要重新定义一个取得关键值key的方法，应该就可以整个重新将数据放一次。不过新的规则还没想到...
最后还是要多动手写代码，可以实际操作一下。