散列表

直接寻址列表 direct-address table

假设有动态集合，元素取自U={0,1，...，m-1}中一个关键字，不重复。

为了表示这个动态集合，可以使用一个直接寻址列表T[0..m-1]进行存储，列表中每一个位置叫做槽slot，slot k point to key k. if k isn't exist, slot k is NIL (T[k]=NIL).

散列表hash table

在直接寻址方式下，关键字k的元素存放在slot k中，在散列表中，存放在slot h(k)中，其中h(x)为散列函数hash function。

通常，全局U总是大于散列表T大小[0,m-1]，所以经过h()散列后，总是会有两个不同的k映射到同一个slot上。解决冲突的办法有链接法(chaining)和开放寻址法(open addressing)

::链接法解决冲突

链接法是把同一个slot中的所有元素都放到一个链表中，这样T就是一个链表的集合。

插入元素x，T(h(x.k)).insert(k)

读取元素x，T(h(x.k)).search(x.k)

删除元素x，T(h(x.k)).delete(k)

其中insert、search、delete都是链表操作

::开放寻址法解决冲突

开放寻址中所有元素都在散列表中，当产生冲突后，会继续寻找下一个slot，查找过程如下<h(k,0), h(k,1), h(k,2), h(k,3)...>，如果存满了，就返回溢出错误。

Insert(T, k)
{
    int i=0;
    do
    {
        int j=h(k, i);
        if(T[j]==null)
        {
            T[j]=k;
            return j;
        }
        else
            i++;
    }while( i==T.Count-1)
    throw new Exception("overflow");
}

Insert(T, k)
{
    int i=0;
    do
    {
        int j=h(k, i);
        if(T[j]==k)
            return j;
        else
            i++;
    }while( T[j]==null || i==T.Count-1)
    return null;
}

这种不适合做删除操作。如果删除后置null，则查找时遇到null就不继续寻找了。通常可以使用一个delete标识表示删除的元素，查找可以绕过，对insert修改使之可以在delete中插入。

线性探查散列函数h(k,i)=(h'(k)+i)%m    (m是散列表的大小)

二次探查散列函数h(k,i)=(h'(k) + c1*i+c2*i*i )%m    (m是散列表的大小, c1和c2是辅助的常数，注意这种查找可能产生循环)

双重散列散列函数h(k,i)=(h'(k) + i*h2(k) )%m  

散列函数hash function

散列函数最好的是均匀散列。如果关键字的范围均匀独立在[0, 1)，h(k)=int(k*m)

余数散列法：h(k)=k%m，通常m应该为素数（如果m=2^n，那么仅使用了k的后n位进行散列）。

乘法散列法：关键字k与常数A相乘，提取小数，然后与m相乘，向下取整，h(k)=int(m*(k*A%1.0))。使用A为黄金分割数被认为很好A=(5^0.5-1)/2=0.6180339887

*全域散列法：没看懂怎么用

*完全散列

关键字存储在列表中之后，不会再改动。