数据结构之哈希表的java实现

哈希表是一种数据结构，提供快速的插入和查找功能。哈希表基于数组存储数据，因此能在O(1)时间内定位数据。关键字值通过哈希函数映射为数组下标。缺点就是数组创建后容量固定，如果数据较多需要不断扩展其长度。
如何将关键字转换为数组下标？这个操作是通过哈希函数完成的。比如,下面就是一个简单的哈希函数，
int hash(int key){
return key % array.length;//通过取余，返回值数组下标
}
有时候，有些哈希函数对于不同的键值可能会生成相同的哈希码值。所以需要解决冲突问题，下面有两种方法：
1.开放地址法：通过在哈希表中再找一个空位来解决此问题。
此法又分为三种方法：
1）线性探测，即上面使用的这种方法，哈希函数将关键字范围压缩到数组的范围，对数组长度取余即可，+1，+2，+3…以此类推进行取余。
2）二次探测的过程是这样，+1，+2，+4，+9…以此类推。
3）再哈希，用不同的哈希函数对关键字再做一次哈希化。

2.链地址法：在哈希表每个单元中设置链表。某个数据项的关键值仍然映射到哈希表的单元中，而数据项本身插入这个单元的链表中其他同样映射到这个位置的数据项只需要加入到链表中。

package test;
public class HashTable {
    Item[] hashArray;
    int arraySize;//定义数组长度
    public HashTable(int size){//构造器，初始化
        arraySize = size;
        hashArray = new Item[arraySize];
    }
    //哈希函数
    public int hash(int key){
        return key % arraySize;
    }
    //插入，这里假设是数组未满，即不能插入大于arraySize的数据数
    public void insert(Item item){
        int key = item.getKey();
        int hashCode = hash(key);
        //若已存在同样的数据，则向下进一位，直到找到空的位置
        //为了简单，也可要求不准有重复数据
        while(hashArray[hashCode] != null){
            ++hashCode;
            hashCode %= arraySize;
        }
        hashArray[hashCode] = item;
    }
    //删除
    public Item delete(int key){
        int hashCode = hash(key);
        while(hashArray[hashCode] != null){
            if(hashArray[hashCode].getKey() == key){
                Item temp = hashArray[hashCode];
                hashArray[hashCode] = null;
                return temp;
            }
            ++hashCode;
            hashCode %= arraySize;
        }
        return null;
    }
    //查找
    public Item find(int key){
        int hashCode = hash(key);
        while(hashArray[hashCode] != null){
            if(hashArray[hashCode].getKey() == key)
                return hashArray[hashCode];
            ++hashCode;
            hashCode %= arraySize;
        }
        return null;
    }
    //列出全部数据
    public void show(){
        for(int i=0;i<arraySize;i++){
            if(hashArray[i] != null)
                System.out.print(hashArray[i].getKey() + " ");
            else
                System.out.print("* ");
        }
    }
    public static void main(String[] args) {
        HashTable ht = new HashTable(10);
        ht.insert(new Item(1));
        ht.insert(new Item(2));
        ht.insert(new Item(3));
        ht.insert(new Item(4));
        ht.insert(new Item(4));
        ht.show();
        Item i = ht.find(3);
        System.out.println("i = "+i.getKey());
        Item di = ht.delete(3);
        System.out.println("di = "+di.getKey());
        ht.show();
    }
}
//定义哈希表中存放的数据类型，可以为任意的类型
class Item{
    int idata;
    public Item(int idata){
        this.idata = idata;
    }
    public int getKey(){
        return idata;
    }
}