基于散列的查找

    基于散列的查找，最好情况是O(1)，平均情况O(1)，最坏情况O(n)。
    使用散列函数来将目标元素的一个或者多个特征转换成一个值，这个值用来索引一个已经索引的散列表。
    基于散列的查找包括：

• 可能键值的全值U。每一个元素e属于C（n个元素的集合C），e将映射到一个键值k，k属于U；
• 散列表A存储着原始集合C的n个元素。A也许包含着元素本身或者也包含了元素的键值。在A中有b个位置；
• 散列函数hash，使用key(e)计算一个整数索引h。

loadTable(size, C)
    A = new array of given size
    for i=0 to n-1 do
        h = hash(C[i])
        if(A[h] is empty) then
            A[h] = new Linked List
        add C[i] to A[h]
    return A
end

search(A, t)
    h = hash(t)
    list = A[h]
    if(list is empty) then
        return false
    if(list contains t) then
        return true
    return false
end

    不适当的散列函数可能会导致一个不均匀的键值分布。散列表中的很多桶会是没有使用过的，浪费空间，而使用的桶会因为多个键值同时映射到一个桶中，导致了大量的冲突，性能遭到影响。

    定义一个函数来计算字符串s的键值。这个键值函数的一个目标是产生足够多的不同值，不过并不要求
这些值是唯一的。根据初始字符串的每一块信息来产生值：
    key(s) = s[0]*31^(len-1) + s[1]*31^(len-2) + ... + s[len-1]

java hashCode样例：
public int hashCode()
{
    int h = hash;
    if(0 == h)
    {
        for(int i=0; i        {
            h = 31 * h + chars[i];
        }
        hash = h;
    }
        
    return h;
}

    hashCode方法尽量尝试优化，它缓存了已经计算的散列值，避免重复计算。
    一个完美的散列函数能够保证在一个特定的键值集合中没有冲突产生。A的大小通常一个素数，但实践中一个好的选择是(2^k)-1，即使这个值并不是素数。则b=(2^k)-1，hash(s)=key(s)%b。

在散列表中查找元素可以分为3部分：

• 计算散列值；
• 通过散列值索引到相应元素；
• 如果有冲突，那么寻找到需要找的元素。

java实现：
//加载散列表
public void load(Iterator it)
{
    listTable = (LinkedList[]) new LinkedList[tableSize];
    while(it.hasNext())
    {
        V v = it.next();

        int h = hashMethod.hash(v);
        if(null == listTable[h])
        {
            listTable[h] = new LinkedList();
        }
        LinkedList list = (LinkedList)listTable[h];
        list.add(v);
    }
}

//查找元素
public boolean search(V v)
{
    int h = hashMethod.hash(v);
    LinkedList list = (LinkedList)listTable[h];
    if(null == list)
    {
        return false;
    }
    return list.contains(v);
}

int hash(V v)
{
    int h = v.hashCode();
    if(h < 0)
    {
        h = 0 - h;
    }
    return h % tableSize;
}

参考：《算法技术手册》