哈希表的分离链接法
原理
Hash Table可以看作是一种特殊的数组。他的原理基本上跟数组相同,给他一个数据,经过自己设置的哈希函数变换得到一个位置,并在这个位置当中放置该数据。哦对了,他还有个名字叫散列
0 | 1 |
---|---|
数据1 | 数据2 |
就像这个数组,0号位置放着数据1,1号位置放数据2
而我们的哈希表则是通过一个函数f(x) 把数据1变成0,把数据2变成1,然后在得到位置插入数据1和数据2。
非常重要的是哈希表的长度为素数最好!!
而且当插入数据大于一半的时候我们要进行扩充!!!
冲突问题产生
现在这个表就是2个数据,所以不会产生什么冲突,但是若一个数据他通过f(x)计算得到的位置也是0呢?是不是就跟数据1产生了冲突,因为数据1已经占据了这个位置,你无法进行插入操作。对不对。
所以我们该如何解决这个问题呢,诶,我们肯定是想两个都可以插入是不是,就像一个炸串一样把他串起来。如图
a b c就像一个炸串,而如何实现这个炸串就有多种方式。这里我们用线性表来实现
线性表实现
我们可以用java自带的List ArrayList等表,这边也给出单链表的实现方式。
publicclassMyArray<AnyType>{
我们首先得创建一个内部类用来存放数据,以及保存下个节点
classArrayNode<AnyType>{publicAnyType data;publicArrayNode<AnyType> next;publicArrayNode(AnyType data){this(data,null);}privateArrayNode(AnyType data,ArrayNode<AnyType> next){this.data=data;this.next=next;}}//save type node;
设置我们这个线性表所需要的对象,例如size和一个头节点,以及我们要进行初始化,判断这个表是否为空等。
privateint theSize;//array list sizeprivateArrayNode<AnyType> head;//head node every data behind it//init MyArraypublicMyArray(){doClear();}publicvoidclear(){doClear();}privatevoiddoClear(){
theSize=0;
head=newArrayNode<>(null);}//get size and is emptypublicintsize(){return theSize;}publicbooleanisEmpty(){return theSize==0;}
接下来我们需要实现他的基本操作,是否包含,插入,获得以及删除。
//containpublicbooleancontains(AnyType x){ArrayNode<AnyType> newNode=head;//get a new node=headwhile(newNode.next!=null){
newNode=newNode.next;if(newNode.data== x)returntrue;}returnfalse;}//get the data in idx from arraypublicAnyTypeget(int idx){returnget(idx,head).data;}privateArrayNode<AnyType>get(int idx,ArrayNode<AnyType> node){if(idx<0||idx>size())thrownewIndexOutOfBoundsException();//out of lengthArrayNode<AnyType> newNode=node;//find start head.nextfor(int i=0; i< idx; i++)
newNode=newNode.next;return newNode;}//set data into arraypublicvoidset(AnyType x){set(x,head);}privatevoidset(AnyType x,ArrayNode<AnyType> node){ArrayNode<AnyType> newNode=node;while(newNode.next!=null)
newNode=newNode.next;
theSize++;
newNode.next=newArrayNode<>(x);}//removepublicvoidremove(AnyType x){remove(x,head);}privatevoidremove(AnyType x,ArrayNode<AnyType> node){if(!contains(x))return;while(node.next!=null){
node=node.next;if(node.next.data==x)break;}ArrayNode<AnyType> oldNode=node.next;
node.next=null;
node.next=oldNode.next;}}
哈希表实现
publicclassMyHashTable<AnyType>{//define the things that we need to useprivatestaticfinalint DEFAULT_SIZE=10;privateMyArray<AnyType>[] arrays;privateint currentSize;
因为我实现的是学号的存储
也就是带0开头的数据 所以我用字符串
这里这个myHash就是我实现的简单哈希函数,即获得的数据字符串化,得到最后两个字符
privateintmyHash(AnyType x){String s=x.toString();returnInteger.parseInt(s.substring(s.length()-2,s.length()));}
初始化哈希表,设置的默认大小为10,然后进行素数判断,如果它不是素数,那么就找到他的下一个素数作为表的大小。
//init we should ensure that the table size is primepublicMyHashTable(){ensureTable(nextPrime(DEFAULT_SIZE));makeEmpty();}privatevoidensureTable(int x){
arrays=newMyArray[x];for(int i=0; i< arrays.length; i++)
arrays[i]=newMyArray<>();}//make the array emptypublicvoidmakeEmpty(){
currentSize=0;for(MyArray<AnyType> myArray:arrays)
myArray.clear();}//size and emptypublicintsize(){return currentSize;}publicbooleanisEmpty(){return currentSize==0;}
基本方法的实现,插入,获得,删除,包含
//contain xpublicbooleancontains(AnyType x){int position=myHash(x);return arrays[position].contains(x);}//insert xpublicvoidinsert(AnyType x){int position=myHash(x);if(arrays[position].contains(x))return;elseif(arrays[position].size()==0)if(++currentSize>arrays.length)makeBigger();
arrays[position].set(x);}//get idx datapublicMyArray<AnyType>get(int idx){return arrays[idx];}
在这里,如果插入的时候啦,实际的currentSize大于二分之一表的大小了
则进行扩充表
一般扩充表的话,我们是直接两倍两倍扩充的。
//makeBiggerpublicvoidmakeBigger(){MyArray[] oldArray= arrays;
arrays=newMyArray[2* arrays.length];for(int i=0; i< oldArray.length; i++)
arrays[i]= oldArray[i];}
下一个素数查找,如果他是偶数,则给他加1这样可以大大减少开销。
然后进行下一个素数判断,奇数当中找素数。
//nextPrimeprivateintnextPrime(int i){if(i%2==0)
i++;for(;!isPrime(i); i+=2);//ensure i is jishureturn i;}
是否为素数判断,如果为2则范围true
如果是1或者为偶数则返回false
都不满足则从三开始,他的平方小于输入的数,用奇数进行操作,因为用偶数的话,前面那个2就直接判断了,所以我们用奇数,大大减少开销。
我们也可以设置他的判断条件是小于输入的二分之一,但是我们用平方进行判断大大减少了开销,而且对于奇数来说是十分有效果的。
//is PrimeprivatebooleanisPrime(int i){if(i==2||i==3)returntrue;if(i==1||i%2==0)returnfalse;for(int j=3; j*j<=i; j+=2)if(i%j==0)returnfalse;returntrue;}}
测试
publicclass test{publicstaticvoidmain(String[] args){MyHashTable<String> a=newMyHashTable<>();
a.insert("001");
a.insert("01");for(int i=1;i<a.get(1).size()+1;i++){System.out.println(a.get(1).get(i));}}}