哈希

引论

哈希(Hashing)是以一种能以常数平均时间进行插入,查找,删除的技术。常数时间一般意义上是指O(1)。

是的,Hashing是一种技术,从英文名也可以看出,这是动名词,一般动名词大多表示的不是一个静态的东西。就像抽象数据结构(ADT),ADT是一系列的操作的集合。而不应该是一般以为的抽象的一种数据结构。可见不同语言的表示以及翻译是一件很重要的事情。扯远了,回到正题。

不同于二叉查找树,二叉查找树有很多的操作,像什么找最大,找最小等等;哈希只有简单的插入,查找,删除这3种操作,而且哈希并不能支持排序信息,也就是在哈希表中的信息都是无序的。但是哈希最大的优点就是执行插入,查找,删除这3种操作只需要常数时间,这是什么概念呢,基本是瞬时啊,尤其对于查找,二叉树的查找的平均时间是O(logN),都认为是很快很有效的了,而哈希表的查找时间是O(1)。这就是价值所在。可以有很多的缺点,但是只有有一个优点无人能及就够了。

哈希的应用很广泛,主要利用的就是它查找很快的优点。

例如编译器对于声明的变量的检查,声明了新的变量,只要O(1)的时间就可以插入;要查询某个变量是否被声明过,也只需要O(1)的时间就可以知道结果。

哈希的思想

哈希表就是一个固定长度的数组,包含有keys,每个key(key可以是字符,字符串,或者是数字,亦或者是什么其他信息等等)都与一个数值(数值一般来说就是0到TableSize-1,TableSize就是哈希表的长度,也就是那个数组的长度)对应。

就像数组原理一样,a[0] = ‘c’; a[0]中包含着字符’c’;哈希表的0位置,包含了一个key, 1位置包含了另一个key等等。当然不会是这样简单,否则就没有必要引入哈希了,数组皆可以了,而且这样也不可能达到上面说的好处。要实现哈希,最重要的部分就是哈希函数。

哈希函数

哈希函数(Hash function)是一个把key映射到数值(也就是0到TableSize-1)的函数。

对于这个函数,一般有两个要求

  • 运算简单

  • 能够把key均匀的映射到数值上(也就是0到TableSize-1),也就是cell里。

哈希函数的格式为:

对于key而言,如果是数值,那么我们直接用就可以了,但是当key是字符串时,这是无法直接用到函数中的,而这也正是最常见的情况。对于这种情况,一种解决方法是把字符串中的字符的ASCII码加起来得到一个数值,将其用于哈希函数。

1
2
3
4
5
6
7
Index Hash(const char *key,int TableSise)
{
unsigned int HashVal = 0;
while(*key!='\0')
HashVal += *key++;
return HashVal%TableSize;
}

而对于TableSize,一般来说要取质数,这样可以比较平均的做hashing。例如我们去TableSize=10;而我们的数据都是10的整数倍的话,那么所有的数据都会被映射到同一个cell上,这是不利于均匀分布的。

另外一种比较好的hash函数是:

$ \sum^{KeySize - 1}_{i = 0} key[KeySize - i - 1] * 32^i $

1
2
3
4
5
6
7
Index Hash(const char *key,int TableSize)
{
unsigned int HashVal = 0;
while(*key!='\0')
HashVal = (HashVal<<5) + *key++;
return HashVal%TableSize;
}

冲突

有了哈希的思想,也有了哈希的手段(哈希函数),那么剩下的问题就是冲突了。在哈希中,冲突时一个很常见的问题,因为数组的大小是有限的,而key是无限的;而且当用哈希函数映射时,不同的key映射到同一个cell(也就是同一个值)是很常见的事情,因此应对这种冲突是Hashing一个最基本的问题。

主要的方法有两种

  • 分离链表法(separate chain)

  • 开放地址法(open addressing)

下面来一个个的分析。

分离链表法(separate chain)

分离链表法的思想极其简单,就是在每个哈希表的cell中引出一个链表,实际的cell中存放的是链表的头指针,数据存放在链表中,当有冲突数据产生,在链表中加入数据就好了。如下图所示:

hash

代码实现:

  • 哈希表定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct ListNode;
typedef struct ListNode *List;
typedef struct ListNode *Position;
struct HashTbl;
typedef struct HashTbl *HashTable;

struct ListNode
{
ElementType Element;
Position Next;
}

struct HashTbl
{
int TableSize;
List *TheLists;
}

从代码定义可以看出,哈希表主要就是包含两个东西,一个是表的大小,另一个是一个数组,这个数组中包含的元素是指针,这些指针是链表的头结点,即也是一个指针。而这里,对数组的定义也是采用的指针形式:
List *TheLists;
因此TheLists其实是指向指针的指针。从上面的定义我们就能看出哈希表的一个整体的结构。

  • 哈希表的初始化
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    HashTable InitializeTable(int TableSize)
    {
    HashTable H;
    int i;
    if(TableSize<MiniSize)
    {
    Error("Table size too small!!");
    return NULL;
    }
    H = malloc(sizeof(struct HashTbl));
    if(H==NULL)
    Error("Out of Space!!");
    // The TableSize should be prime
    H->TableSize = NextPrime(TableSize);
    // H->TheLists is a pointer point to Array consists of pointer that point to list
    H->TheLists = malloc(sizeof(List)*H->TableSize);
    if(H->TheLists==NULL)
    Error("Out of Space!!");

    //header
    for(i=0;i<TableSize-1;i++)
    {
    H->TheLists[i] = malloc(sizeof(struct ListNode));
    if(H->TheLists[i]==NULL)
    Error("Out of Space!!");
    else
    H->TheLists[i]->Next = NULL;
    }
    return H;
    }

初始化就是定义哈希表的大小,让哈希表的数组中包含头结点,然后将头结点指向NULL。并做一些质数约束等等。

  • 哈希表的查找Find
1
2
3
4
5
6
7
8
9
10
11
Position Find(ElementType Key,HashTable H)
{
Position P;
List L;
//find the position in HashTable
L = H->TheLists[Hash(Key,H->TableSize)];
P = L->Next;
while(P!=NULL && P->Element != Key)
P = P->Next;
return P;
}

查找的顺序就是先找到哈希表中的位置,然后再在对应的链表里查找。

  • 哈希表的插入:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Insert(ElementType Key,HashTable H)
{
Position P,NewP;
List L;
P = Find(Key,H);
if(P==NULL)
{
NewP = malloc(sizeof(struct List));
if(NewP==NULL)
Error("Out of Space!!!");
else
{
// //Find the position in HashTable
L = H->TheLists[Hash(Key,H->TableSize)];
// Insert the Key after the header
NewP->Next = L->Next;
NewP->Element = Key;
L->Next = NewP;
}

}
}`

插入的做法是:先查找看hash表中有没有key,如果有的话就do nothing。否则的话就要增加节点。首先找到hash表中的位置,然后在链表表头处插入节点。关于为什么在表头处插入,主要有两点原因

  1. 表头处插入比较省时,不需要再去遍历链表了
  2. 新插入的Key在下次被访问的概率很大。这个类似的结论在计算机的各个部分很普遍。
  • 哈希表的删除:
    分离链表法的删除Key的方法,思想等同于在链表中删除节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Delete(ElementType Key,HashTable H)
{
Position P,NP;
List L;
L = H->TheLists[Hash(Key,H->TableSize)];

P = L->Next;
while(P->Next != NULL && P->Element != Key)
{
P = P->Next;
if(P->Element == Key)
{
NP = P_>Next;
P->Next = NP->Next;
free(NP);
}
}
}

开放地址法(open addressing)

开放地址法的思想在于当一个冲突发生时,去查找下一个空的cell来装这个key,这个查找是有规矩的。这个思想的实现基于下面的哈希函数

$F(i)$就是查找下一个空的位置所要遵循的约束。

开放地址法一般有三种形式,这是根据F(i)的形式分的

  • 线性探测法,即F(i) = i;

  • 平方探测法,即F(i)=i*i;

  • 双哈希探测法,即F(i) = i*hash2(X);

开放地址法的优点就是所有的数据Key都在Hash表的表内,不需要因为外部的链表来处理冲突。但是这个表要足够大,一般要达到数据量Key的2倍。

线性探测法,即$F(i) = i$;

hash

平方探测法,即$F(i)=i*i$;

平方探测比线性探测法要节省时间,比较快,但是对于平方探测法,当数据量大于哈希表的大小的一半时,就会失效,这个很明显。

hash

双哈希探测法,即$F(i) = i*hash2(X)$;

这个方法的难度在于怎样选取hash2(X);这个函数选择不好的话,就别想得到好的结果了。

hash

代码实现(以平方探测为例子)

  • 哈希表定义:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    typedef unsigned int Index;
    typedef Index Position;
    struct HashTbl;
    typedef struct HashTbl *HashTable;


    enum KindofEntry {Legitimate,Empty,Deleted};
    struct HashEntry
    {
    ElementType Element;
    enum KindofEntry Info;
    };


    typedef struct HashEntry Cell;


    struct HashTbl
    {
    int TableSize;
    Cell *HashCell;
    };

这个定义中,对每一个hash小cell中有两个东西,一个是Key,另一个是状态信息。哈希表也有两个结构,一个是哈希表的大小,另一个是指向存储哈希表的第一个单元的指针。

  • 哈希表初始化:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    HashTable InitializeTable (int TableSize)
    {
    HashTable H;
    if(TableSize<MiniSize)
    {
    Error("TableSize too Small!!");
    return NULL;
    }
    H = malloc(sizeof(struct HashTbl));
    if(H==NULL)
    Error("Out of Space!!!");
    H->TableSize = NextPrime(TableSize);
    H->HashCell = malloc(sizeof(struct HashEntry)*H->TableSize);
    if(H->HashCell == NULL)
    Error("Out of Space!!!");
    int i;
    for(i=0;i<H->TableSize;i++)
    H->HashCell[i].Info = Empty;
    return H;
    }
  • 哈希表的查找Find:

1
2
3
4
5
6
7
8
9
10
11
12
13
Position Find(ElementType Key,HashTable H)
{
Position P;
P = hash(Key,H->TableSize);
int i=0; //collision funciton F(i)=i*i = F(i-1)+2*i-1;
while(H->HashCell[P].Info!=Empty && H->HashCell[P].Element!=Key)
{
P += 2*++i -1;
if(P>H->TableSize)
P -= H->TableSize;
}
return P;
}

如果Key没在hash表中的话,这个函数是没办法表达这个的,它只能返回位置P,P要么是找到的值得位置,要么是这个位置的状态是Empty。这要下面的插入删除程序自己判断得知。

  • 哈希表的插入Insert:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void Insert(ElementType Key,HashTable H)
    {
    Position P;
    P = Find(Key,H);
    if(H->HashCell[P].Info!=Legitimate)
    {
    H->HashCell[P].Info == Legitimate;
    H->HashCell[P].Element = Key;
    }
    }

只要判断P的位置没有Key,就可以插入Key。

  • 哈希表的删除Delete:
1
2
3
4
5
6
7
8
9
void Delete(ElementType Key,HashTable H)
{
Position P;
P = Find(Key,H);
if(H->HashCell[P].Info == Legitimate)
{
H->HashCell[P].Info == Delete;
}
}

哈希表的删除采用懒惰删除,懒惰删除(lazy deletion)指的是从一个哈希表中删除 元素的一种方法。在这个方法中,删除仅仅是指标记一个元素被删除,而不是整个清除它。被删除的位点在插入时被当作空元素,在搜索之时被当作已占据。因此只要把要删除的Key的位置标记为delete就可以了。

重新哈希

Refresh Hashing的提出是基于这样的一个背景问题:当我们采用平方探测的开放地址法时,随着插入Key的增多,运行的效率会变得越来越慢(因为会有更多的冲突需要处理)而随着key的数目超过TableSize的一半时,这种方法有可能要失效,并且及时能够再次插入,效率也都要降低的可怕,因此引入了Refresh Hashing,急重新哈希。

思想:我们把一个插入Key过多的表重新哈希到一个TableSize是原表2倍大的新的哈希表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
HashTable Rehash(HashTable H)
{
int i;
int OldSize;
Cell *OldCell;
OldCell = H->HashCell
OldSize = H->TableSize;
H = InitializeTable(2*OldSize);
for(i=0;i<OldSize;i++)
{
if(OldCell[i].Info == Legitimate)
Insert(OldCell[i].Element,H);
}
free(OldCell);
return H;
}

这个程序做的事情就是把旧的Key取出来,映射到新的哈希表中。
关于到底什么时候Refresh Hash,一般有三种选择

  • 哈希表已经装满了一半了
  • 插入失败的时候
  • 当哈希表达到一个临界的载入因子的时候,这个是一个折中的方法。

载入因子

载入因子(Load Factor)是指表中Key的个数与哈希表的TableSize的比值。在Hash method中,这个才是最重要的概念,因为载入因子直接影响到哈希表的效率。

我们在分离链表法中,尽量要使载入因子=1,只有这样才能保证平均O(1)的时间复杂度,如果载入因子很大的话,那么表明会有很多Key插入到了链表中,链表会比较深,那么就不可能有平均O(1)的时间复杂度。

在开放地址法中,我们要尽量让载入因子<0.5.否则平方探测法有可能失效。同时,无论是线性还是平方探测,当载入因子过大时,因为要处理很多的冲突,那么必然要导致时间花费,故很难保证平均O(1)的时间复杂度。所以当载入因子比较大时,要果断Refresh Hashing。

总结

哈希表的操作只有查找,插入,删除这几种。哈希表是没有排序信息的,如果需要排序信息,请绕道。因为很多的应用是不需要排序信息的,只需要快速的查找,因此哈希表具有很大的优势。哈希表的平均时间复杂度为O(1),这是非常理想的。

哈希表中最重要的是冲突的处理,有分离链表法和开放地址法。因为冲突的处理uhi影响查找的速度,因此要尽量使载入因子取合理的值,以减少冲突的处理次数。

刚开始接触哈希表时,根本就搞不清楚这是怎么一回事,怎么可以是O(1)时间。当时完全被链表,树那些数据结构给思维禁锢了。其实哈希表时用了数学函数的映射方法使得能在O(1)时间内查找。给定一个输入,直接输入到函数,就可以得到它的位置,直接到这个位置找就可以了(有冲突时,需要按照冲突的规矩向下查找),所以可以达到O(1)的时间。

显示 Gitment 评论