一道double hashing面试测验题，小弟不会，巨汗，望高手相救

Question

小弟以前是搞PB的，准备转行学java，刚学才一个月不到。上午壮胆冒死参加一公司面试，该公司专搞j2ee的，面试官得知我刚学java不久，倒也没太为难我，只是出了几道基础题让我做，明天中午前给他结果。其中就有这么一道：
Write a program that implements insertion and deletion of hash table by double hashing.
( Modify HashTable.java )
附带有三个文件：
文件一：HashTableMain.java
class HashTableMain
{
    public static void main(String[] args){
        DataItem aDataItem;
        HashTable theHashTable = new HashTable(30);
//
        aDataItem = new DataItem(10);
        theHashTable.insert(aDataItem);
        theHashTable.displayTable();
        //
        aDataItem = new DataItem(11);
        theHashTable.insert(aDataItem);
        theHashTable.displayTable();
        //
        DataItem dDataItem = theHashTable.delete(11);
        theHashTable.displayTable();
        System.out.println(dDataItem.iData + " was deleted.");
    }
}
文件二：DataItem.java
class DataItem
{
    int iData;    public DataItem(int ii){
        iData = ii;
    }
}
文件三：HashTable.java
class HashTable
{
    DataItem[] hashArray;
    int arraySize;
    DataItem nonItem;    public HashTable(int size){
        arraySize = size;
        hashArray = new DataItem[arraySize];
        nonItem = new DataItem(-1);
    }    void displayTable(){
        System.out.print("Table: ");
        for(int j=0;j<arraySize;j++){
            if(hashArray[j] != null)
                System.out.print(hashArray[j].iData+" ");
            else
                System.out.print("** ");
        }
        System.out.println("");
    }    int hashFunc(int key){
        return key % arraySize;
    }    void insert(DataItem item){
        int key = item.iData;
        int hashVal = hashFunc(key);
        while(hashArray[hashVal] != null &&
              hashArray[hashVal].iData != -1)
            {
                hashVal++;
                hashVal %= arraySize;
            }
        hashArray[hashVal]=item;
    }
    
    DataItem delete(int key){
     int hashVal = hashFunc(key);
     while(hashArray[hashVal] != null){
     if(hashArray[hashVal].iData == key){
     DataItem temp = hashArray[hashVal];
     hashArray[hashVal] = nonItem;
     return temp;
     }
     hashVal++;
     hashVal %= arraySize;
     }
     return null;
}
}
怎么和我学的有关hashtable的概念不一样啊？hashtable不是有put和remove的方法吗，为什么还要人工写个insert和delete方法？还有这个double hashing，我现在连基本知识还没弄明白呢。怎么通过修改HashTable.java这个文件实现？望高手相救!! 100分相送~~~

Answer 1

汗，他们公司还用hashmap啊，这是java 1的容器，
现在都用hashmap,还有，他之所以重写insert和delete，就是为了把hashtable的方法封装了。

Answer 2

1.这不是java的Hashtable,而是他们自己模仿写的.仔细看看java的Hashtable的t是小写,而他们是HashTable.
2.什么叫double hashing
Hashtable使用的哈希函数难免会遇到hash冲突(原理见数据结构课本),Hashtable类使用double hashing来解决冲突.
double hashing的工作原理如下：有一个包含多个哈希函数（H1……Hn）的集合。当我们要从哈希表中添加或获取元素时，首先使用哈希函数H1。如果导致冲突，则尝试使用H2，一直到Hn。各个哈希函数不同的是它们选用的乘法因子。

Answer 3

这个自定义的HashTable的hash函数很简单:
int hashFunc(int key){
    return key % arraySize;
}
这样很容易会遇到hash冲突,这个例子遇到hash冲突是之后是把key+1调用此函数再hash,你可以写一个另外的hash函数
int hashFuncN(int key , int nMultiply){
    int hashCode = (new Integer(key)).hashCode();
    return (hashCode + nMultiply*(1 + (((hashCode>> 5) + 1) % (arraySize – 1)))) % arraySize;
}
插入元素时，必须查找内容为空的位置，如果查找的位置内容非空,则冲突,使用hashFuncN函数;
void insert(DataItem item){
if (null==item){
 return;
}
int key = item.iData;
int hashVal = hashFunc(key);
         DataItem iTempItem = hashArray[hashVal];
if ( iTempItem!= null &&iTempItem.iData != -1){
for (int j =1 ; j<arraySize  ; ++j){
 hashVal = hashFuncN(key,j);
 iTempItem = hashArray[hashVal];
 if ( iTempItem!= null &&iTempItem.iData != -1){
 continue;
 } else {
                  break;
 }
}
hashArray[hashVal]=item;
} else {
   hashArray[hashVal]=item;
}
}

Answer 4

成功啦，的确如laughsmile所说所写的，基本不用怎么修改，直接在JCreater中编译运行通过。
下面是我按照laughsmile的指点，修改后的HashTable.java文件源码，感兴趣的朋友们可以看看：
HashTable.javaclass HashTable
{
    DataItem[] hashArray;
    int arraySize;
    DataItem nonItem;    public HashTable(int size){
        arraySize = size;
        hashArray = new DataItem[arraySize];
        nonItem = new DataItem(-1);
    }    void displayTable(){
        System.out.print("Table: ");
        for(int j=0;j<arraySize;j++){
            if(hashArray[j] != null)
                System.out.print(hashArray[j].iData+" ");
            else
                System.out.print("** ");
        }
        System.out.println("");
    } int hashFunc(int key){
    return key % arraySize;
}
    int hashFuncN(int key , int nMultiply){
    int hashCode = (new Integer(key)).hashCode();
    return (hashCode + nMultiply*(1 + (((hashCode>> 5) + 1) % (arraySize - 1)))) % arraySize;
}    void insert(DataItem item){
if (null==item){
 return;
}
int key = item.iData;
int hashVal = hashFunc(key);
         DataItem iTempItem = hashArray[hashVal];
if ( iTempItem!= null &&iTempItem.iData != -1){
for (int j =1 ; j<arraySize  ; ++j){
 hashVal = hashFuncN(key,j);
 iTempItem = hashArray[hashVal];
 if ( iTempItem!= null &&iTempItem.iData != -1){
 continue;
 } else {
                  break;
 }
}
hashArray[hashVal]=item;
} else {
   hashArray[hashVal]=item;
}
}    
    DataItem delete(int key){
     int hashVal = hashFunc(key);
     while(hashArray[hashVal] != null){
     if(hashArray[hashVal].iData == key){
     DataItem temp = hashArray[hashVal];
     hashArray[hashVal] = nonItem;
     return temp;
     }
     hashVal++;
     hashVal %= arraySize;
     }
     return null;
}
}

Answer 5

这是我在网上所能找到的对Double Hashing最精确详实的描述，对我理解laughsmile的说明和代码起了很大作用：
http://www.cnblogs.com/wayfarer/archive/2004/04/12/5852.aspx

Answer 6

面试还算顺利通过了，但无论是否能收到通知，我心里都很开心，因为我又学到了不少东西，同时又学得还有很多很多要学：比如那个乘法因子nMultiply的取值问题，就够我回味好一阵子的，呵万分感谢laughsmile！~~也非常感谢这么多关注并帮忙up的朋友们~~~