精华内容
下载资源
问答
  • 哈希

    千次阅读 2016-12-07 17:26:42
    0、引入 哈希表支持一种最有效的检索方法:散列。从根本上来说,一个哈希表包含一个数组,通过特殊的索引值(键)来访问数组中的...由于计算哈希值和在数组中进行索引都只消耗固定的时间,因此哈希表的最大亮点在于它是

    0、引入

    哈希表支持一种最有效的检索方法:散列。从根本上来说,一个哈希表包含一个数组,通过特殊的索引值(键)来访问数组中的元素。哈希表的主要思想是通过一个哈希函数,在所有可能的键与槽位之间建立一张映射表。哈希函数每次接受一个键将返回与键相对应的哈希编码或哈希值。键的数据类型可能多种多样,但哈希值的类型只能是整型。

    由于计算哈希值和在数组中进行索引都只消耗固定的时间,因此哈希表的最大亮点在于它是一种运行时间在常量级的检索方法。当哈希函数能够保证不同的键生成的哈希值互不相同时,就说哈希表能直接寻址想要的结果。但这只是理想的状态,在实际运用过程中,能够直接寻址结果的情况非常少。例如,一个电话邮件系统,通过8个字符组成的名字作为键,来哈希得到系统中的用户信息。如果我们想依赖直接寻址,那么这个哈希表将会有超过26^8=2.09×10^11个条目,而这些条目中的绝大多数都是无用的,因为大多数的字符组合都不是姓名。

    通过与各种各样的键相比,哈希表的条目数相应较少。因此,绝大多数哈希函数会将一些不同的键映射到表中相同的槽位上。当两个键映射到一个相同的槽位上时,它们就产生了冲突。一个好的哈希函数能最大限度地减少冲突,但冲突不可能完全消除,我们仍然要想办法处理这些冲突。


    1、链式哈希表的描述

    链式哈希表从根本上来说是由一组链表构成。每个链表都可以看做一个"桶",我们将所有的元素通过散列的方式放到具体的不同的桶中(见下图)。插入元素时,首先将其键传入一个哈希函数(该过程称为哈希键),函数通过散列的方式告知元素属于哪个"桶",然后在相应的链表头插入元素。查找或删除元素时,用同样的方式先找到元素的"桶",然后遍历相应的链表,直到发现我们想要查找的元素。因为每个"桶"都是一个链表,所以链式哈希表并不限制包含元素的个数。然而,如果表变得太大,它的性能将会降低。

    链式哈希表

    解决冲突

    当哈希表中两个键散列到一个相同的槽位时,这两个键之间将会产生冲突。链式哈希表解决冲突的方法非常简单:当冲突发生时,它就将元素放到已经准备好的"桶"中。但这同样会带来一个问题,当过多的冲突发生在同一槽位时,此位置的"桶"将会变得越来越深,从而造成访问这个位置的元素所需要的时间越来越多。

    在理想情况下,我们希望所有"桶"以几乎同样的速度增长,这样它们就可以尽可能地保持小的容量和相同的大小。换句话说,我们的目标就是尽可能地均匀和随机地分配表中的元素,这种情况在理论上称为均匀散列,而在实际中,我们只能尽可能近似达到这种状态。

    如果想插入表中的元素数量远大于表中"桶"的数量,那么即使是在一个均匀散列的过程中,表的性能也会迅速降低。在这种情况下,表中所有的"桶"都变得越来越深。因此,我们必须要特别注意一个哈希表的负载因子,其定义为:

    α=n/m

    其中,n是表中元素的个数,m是"桶"的个数。在均匀散列的情况下,链式哈希表的负载因子告诉我们表中的"桶"能装下元素个数的最大值。

    例如,有一个链式哈希表,其"桶"的数量m=1599,元素的数量n=3198,其负载因子α=3198/1599=2。所以在这种情况下,当查找元素时,可能每个"桶"里面的元素不会超过两个。当有一个表的负载因子小于1时,这个表每个位置所包含的元素不超过一个。当然,由于均匀散列是一个理想的近似情况,因此在实际情况中我们往往多少会检索超过负载因子建议的数值。如何达到更接近于均匀散列的情况,最终取决于如何选择哈希函数。

    选择哈希函数

    一个好的哈希函数旨在近似均匀散列,也就是,尽可能以均匀和随机的方式散布一个哈希表中的元素。定义一个哈希函数f,它将键k映射到哈希表中的位置x。x称为k的哈希编码,正式的表述为:

    h(k)=x

    一般来说,大多数的散列方法都假设k为整数,这样k能够很容易地以数学方式修改,从而使得h能够更均匀地将元素分布在表中。当k不是一个整数时,我们也可以很容易地将它强制转换为整型。

    如何强制转换一组键,很大程度上取决于键本身的特点。所以,在一个特定的应用中,尽可能地获取键的特性显得尤为重要。例如:如果我们想对程序中的标识符进行散列,会发现程序中有很多相似的前缀和后缀,假使开发人员倾向于将变量声明为类似sampleptr、simpleptr、sentryptr的名字。我们可以严格按照键的开头和结尾字符来强制转换,但这显然不是一个好的方法,因为对于一个k会有多个标识符与之对应。另一方面,我们不妨随机地从4个位置来选择字符,然后随机地改变它们的顺序,并将它们封装到一个4字节的整数中。要记住,无论用什么方法来强制转换键,目的都是尽可能选择一个能将键均匀、随机地分布到表中的哈希函数。

    取余法

    有一个整型键k,一种最简单地将k映射到m个槽位的散列方法是计算k除以m的所得到的余数。我们称之为取余法,正式的表述为:

    h(k) = k mod m

    如果表有m=1699个位置,而要散列的键k=25657,通过这种方法可以得到哈希编码为25657 mod 1699=172。通常情况下,要避免m的值为2的幂。这是因为假如m=2^p,那么h仅仅是k的p个最低阶位。通常我们选择的m会是一个素数,且不要太接近于2的幂,同时还要考虑存储空间的限制和负载因子。(使用取余法的一个经验是,通常m为小于或等于表长(最好接近表长)的最小质数或不包含小于20质因子的合数。)

    例如,如果我们想往一个链式哈希表中插入n=4500个左右的元素,会选择m=1699(m是一个介于2^10~2^11之间的素数)。由此可以计算出它的负载因子α=4500/1699≈2.6,根据均匀散列表述,这说明表中每个"桶"大概能容纳2~3个元素。

    乘法

    与取余法不同的是乘法,它将整型键k乘以一个常数A(0<A<1);取结果的小数部分;然后乘以m取结果的整数部分。通常情况下,A取0.618,它由√5减1再除以2得到。这个方法称为乘法,正式的表述为:

    h(k)=⌊m(kA mod 1)⌋,其中A=(√5 - 1)/2≈0.618

    这种方法有个优点是,对于表中槽位个数m的选择并不需要像取余法中那么慎重。例如:如果表有m=2000个位置,散列的键k=6341,那么得到的哈希编码为2000×(6341×0.618 mod 1)=2000×(3918.738 mod 1)=2000×0.738=1476。

    在链式哈希表中,如果期望插入的元素个数不超过n=4500个,可以让m=2250.这样得到的负载因子α=4500/2250=2,根据均匀散列的规则,在每个"桶"中存储的元素个数一般不超过两个。同时请注意,这个散列方法可以让我们更灵活地选择m,以便获取我们可以接受的最大"桶"深。

    下面的代码列举了一个能够较好地处理字符串的哈希函数。它通过一系列的位操作将键强制转换为整数。最后结果是通过取余法来得到的。这个哈希函数针对哈希字符串执行得很好。(此函数改编自《Compilers: Principles, Techniques, and Tools》,是为编译器所写的一个哈希函数。)

    // 一个适用于处理字符串的哈希函数
    
    /* hashpjw.c */
    
    #include "hashpjw.h"
    
    /* hashpjw */
    unsigned int hashpjw(const void *key)
    {
        const char *ptr;
        unsigned int val;
    
        /* Hash the key by performing a number of bit operations on it. */
        val = 0;
        ptr = key;
    
        while(*ptr != '\0')
        {
            unsigned int tmp;
            val = (val << 4) + (*ptr);
            
            if(tmp = (val & 0xf0000000))
            {
                val = val ^ (tmp >> 24);
                val = val ^ tmp;
            }
            
            ptr++;
        }
        
        /* In practice, replace PRIME_TBLSIZ with the actual table size. */
        return val % PRIME_TBLSIZ;
    }
    


    2、链式哈希表的接口定义

    chtbl_init

    ——————

    int chtbl_init(CHTbl *htbl, int buckets, int (*h)(const void *key), int (*match)(const void *key1, const void *key2), void (*destroy)(void *data));

    返回值:如果哈希表初始化成功,返回0;否则返回-1。

    描述:初始化htbl指定的链式哈希表。在对链式哈希表进行其他操作之前必须首先调用初始化函数。哈希表中所分配的"桶"的个数将由buckets指定。函数指针h指向一个用户定义的哈希函数,此函数会将键进行散列。函数指针match指向一个用户定义的函数,此函数用于判断两个键是否匹配。如果key1等于key2,返回1;否则返回其他值。参数destroy是一个函数指针,通过在chtbl_destroy中调用来释放动态分配的内存空间。例如,一个哈希表包含使用malloc动态分配内存的数据,那么当销毁此哈希表时,destroy会调用free来释放内存空间。当结构化数据包含若干动态分配内存的数据成员时,destroy应该指向一个用户自定义的函数来释放每个动态分配的数据成员和结构本身的内存空间。如果哈希表中的数据不需要释放,那么destroy应该指向NULL。

    复杂度:O(m),m是哈希表中"桶"的个数。


    chtbl_destroy

    ——————

    void chtbl_destroy(CHTbl *htbl);

    返回值:无

    描述:销毁htbl指定的链式哈希表。在调用chtbl_destroy之后不再允许进行其他操作,除非再次调用chtbl_init。chtbl_destroy会删除哈希表中的所有元素,并当参数destroy不为NULL时释放结构体中成员所占用的内存空间。

    复杂度:O(m),m是哈希表中"桶"的个数。


    chtbl_insert

    ——————

    int chtbl_insert(CHTbl *htbl, const void *data);

    返回值:如果插入元素成功,返回0;如果哈希表已经包含此元素,返回1;否则,返回-1。

    描述:向htbl指定的链式哈希表中插入一个元素。新元素包含一个指向data的指针,只要元素仍然存在于哈希表中,此指针就一直有效。与data相关的内存空间将由函数的调用者来管理。

    复杂度:O(1)


    chtbl_remove

    ——————

    int chtbl_remove(CHTbl *htbl, void **data);

    返回值:如果删除元素成功,返回0;否则,返回-1。

    描述:从htbl指定的链式哈希表中删除与data匹配的元素。返回时,data指向已删除元素中存储的数据。与data相关的内存空间将由函数的调用者来管理。

    复杂度:O(1)


    chtbl_lookup

    ——————

    int chtbl_lookup(const CHTbl *htbl, void **data);

    返回值:如果在哈希表中找到元素,返回0;否则,返回-1。

    描述:查找htbl指定的链式哈希表中是否有与data相匹配的元素。如果找到,在函数返回时,data将指向哈希表中相匹配元素中的数据。

    复杂度:O(1)


    chtbl_size

    ——————

    int chtbl_size(CHTbl *htbl);

    返回值:哈希表中元素的个数。

    描述:获取htbl指定的链式哈希表元素个数的宏。

    复杂度:O(1)


    3、链式哈希表的实现与分析

    链式哈希表包含一组"桶",每个"桶"其实是一个链表,链表用来存储散列到表中某些槽位的元素。结构CHTbl是链式哈希表的数据结构。这个结构包含6个成员:buckets指明表中分配的"桶"的个数;h、match和destroy用于封装传入chtbl_init函数的函数;size指明表中现有元素的数量;table是存储"桶"的数组。

    // 链式哈希表抽象数据类型的头文件
    
    /* chtbl.h */
    
    #ifndef CHTBL_H
    #define CHTBL_H
    
    #include <stdlib.h>
    
    #include "list.h"
    
    /* Define a structure for chained hash tables. */
    typedef struct CHTbl_
    {
        int buckets;
    
        int (*h)(const void *key);
        int (*match)(const void *key1, const void *key2);
        void (*destroy)(void *data);
    
        int size;
        List *table;
    } CHTbl;
    
    /* Public Interface */
    int chtbl_init(CHTbl *htbl, int buckets, int (*h)(const void *key), int (*match)(const void *key1, const void *key2), void (*destroy)(void *data));
    
    void chtbl_destroy(CHTbl *htbl);
    
    int chtbl_insert(CHTbl *htbl, const void *data);
    
    int chtbl_remove(CHTbl *htbl, void **data);
    
    int chtbl_lookup(const CHTbl *htbl, void **data);
    
    #define chtbl_size(htbl) ((htbl)->size)
    
    #endif // CHTBL_H
    

    // 链式哈希表的实现
    
    /* chtbl.c */
    
    #include <stdlib.h>
    #include <string.h>
    
    #include "list.h"
    #include "chtbl.h"
    
    /* chtbl_init */
    int chtbl_init(CHTbl *htbl, int buckets, int (*h)(const void *key), int (*match)(const void *key1, const void *key2), void (*destroy)(void *data))
    {
        int i;
    
        /* Allocate space for the hash table. */
        if((htbl->table = (List *)malloc(buckets * sizeof(List))) == NULL)
            return -1;
    
        /* Initialize the buckets. */
        htbl->buckets = buckets;
        for(i = 0; i < htbl->buckets; i++)
            list_init(&htbl->table[i], destroy);
    
        /* Encapsulate the functions. */
        htbl->h = h;
        htbl->match = match;
        htbl->destroy = destroy;
    
        /* Initialize the number of elements in the table. */
        htbl->size = 0;
    
        return 0;
    }
    
    /* chtbl_destroy */
    void chtbl_destroy(CHTbl *htbl)
    {
        int i;
    
        /* Destroy each bucket. */
        for(i = 0; i < htbl->buckets; i++)
        {
            list_destroy(&htbl->table[i]);
        }
    
        /* Free the storage allocated for the hash table. */
        free(htbl->table);
    
        /* No operations are allowed now, but clear the structure as a precaution. */
        memset(htbl, 0, sizeof(CHTbl));
    
        return;
    }
    
    /* chtbl_insert */
    int chtbl_insert(CHTbl *htbl, const void *data)
    {
        void *temp;
        int bucket, retval;
    
        /* Do nothing if the data is already in the table. */
        temp = (void *)data;
        if(chtbl_lookup(htbl, &temp) == 0)
            return 1;
    
        /* Hash the key. */
        bucket = htbl->h(data) % htbl->buckets;
    
        /* Insert the data into the bucket. */
        if((retval = list_ins_next(&htbl->table[bucket], NULL, data)) == 0)
            htbl->size++;
    
        return retval;
    }
    
    /* chtbl_remove */
    int chtbl_remove(CHTbl *htbl, void **data)
    {
        ListElmt *element, *prev;
        int bucket;
    
        /* Hash the key. */
        bucket = htbl->h(*data) % htbl->buckets;
    
        /* Search for the data in the bucket. */
        prev = NULL;
    
        for(element = list_head(&htbl->table[bucket]); element != NULL; element = list_next(element))
        {
            if(htbl->match(*data, list_data(element)))
            {
                /* Remove the data from the bucket. */
                if(list_rem_next(&htbl->table[bucket], prev, data) == 0)
                {
                    htbl->size--;
                    return 0;
                }
                else
                {
                    return -1;
                }
            }
            prev = element;
        }
    
        /* Return that the data was not found. */
        return -1;
    }
    
    /* chtbl_lookup */
    int chtbl_lookup(const CHTbl *htbl, void **data)
    {
        ListElmt *element;
        int bucket;
    
        /* Hash the key. */
        bucket = htbl->h(*data) % htbl->buckets;
    
        /* Search for the data in the buckets. */
        for(element = list_head(&htbl->table[bucket]); element != NULL; element = list_next(element))
        {
            if(htbl->match(*data, list_data(element)))
            {
                /* Pass back the data from the table. */
                *data = list_data(element);
                return 0;
            }
        }
    
        /* Return that the data was not found. */
        return -1;
    }
    

    chtbl_init

    链式哈希表由chtbl_init初始化,经过初始化的哈希表才能进行其他操作。链式哈希表的初始化过程比较简单,其中,首先为"桶"分配空间;然后调用list_init初始化每个"桶";接着封装h、match和destroy函数;最后将size值设置为0。

    chtbl_init的时间复杂度为O(m),其中m是表中"桶"的个数。这是由于复杂度为O(1)的操作list_init将为每个"桶"执行一次(桶的数量为m)。而剩下的初始化操作都能在固定的时间内完成。


    chtbl_destroy

    链式哈希表由chtbl_destroy进行销毁。函数的主要功能是删除每个"桶"中的元素,然后释放由chtbl_init分配的内存空间。如果传递给函数chtbl_init的参数destroy不为NULL的话,每当一个元素被移除时都要调用一次由destroy所指向的析构函数。

    chtbl_destroy的时间复杂度为O(m),其中m是表中"桶"的个数。这是由于list_destroy操作将为每个"桶"执行一次。在每个桶中,我们希望移除元素的数量和哈希表本身的负载因子相同,这个负载因子通常是一个较小的常数。


    chtbl_insert

    链式哈希表由chtbl_insert向表中插入元素。因为哈希表不允许插入相同的键,所以在插入元素时通常会先调用chtbl_lookup来确保表中没有重复的元素。如果散列表中的元素没有重复的键,将新元素的键散列,然后根据哈希编码将元素插入哈希表中相应位置的"桶"中。如果整个插入过程成功,表的容量将增大。

    假设我们尽量遵从均匀散列的方法,chtbl_insert的时间复杂度为O(1)。这是由于chtbl_insert散列键,并在链表头插入元素的操作都是运行固定时间的运算。


    chtbl_remove

    链式哈希表通过chtbl_remove删除表中的元素。为了删除元素,散列元素的键,查找与元素键相匹配的"桶",然后调用list_rem_next删除元素。根据list_rem_next的要求,在删除之前,prev必须维护一个指向待删除元素的前一个元素的指针。回想一下,在list_rem_next中,data用来指向从列表中删除的数据。如果在"桶"中没有找到匹配的键,那么表明哈希表中没有此元素。如果删除过程成功,将表的大小减一。

    假设我们尽量遵从均匀散列的方法,chtbl_remove的时间复杂度为O(1)。这是因为,在每个"桶"中,我们希望查找与哈希表的负载因子相同数量的元素,这个值通常是一个较小的常量。


    chtbl_lookup

    链式哈希表通过chtbl_lookup查找元素,并返回一个指向对应数据的指针。此操作与chtbl_remove非常类似,只是在查找到元素后它不会执行删除操作。

    假设我们尽量遵从均匀散列的方法,chtbl_lookup的时间复杂度为O(1)。这是因为我们期望查找的元素数量等于哈希表的负载因子,这样所用的代价会更小。


    chtbl_size

    获取链式哈希表的元素数量的宏定义。它通过结构CHTble的size成员来获取元素个数。

    其时间复杂度为O(1),因为访问一个结构的一个成员是一个简单的任务,运行一段固定的时间即可完成。


    4、链式哈希表的例子:符号表

    哈希表的一个重要应用是在编译器中,用来维护程序中出现的符号信息。正规来说,就是编译器将一种编程语言写成程序(例如,源代码是用C语言写的)翻译成另外一种能够在机器上运行的机器编码,为了能够更加有效地管理程序中的符号信息,编译器通常使用一种叫做符号表的数据结构。符号表通常由哈希表来实现,这样就能够满足编译器快速存取符号信息的要求。

    在编译的过程中,编译器访问符号表也分为几个阶段。其中一个部分称为词法分析器,用来插入符号。词法分析器是编译器的重要部分,它负责将源代码中有组织的字符转换为有意义的字符串,称为语义转换。这些转换后的字符串称为标记(token),然后传到解释器进行解析。解释器进行句法分析。送入词法分析器的符号通常是字符流,词法分析器将字符流分割出来存入符号表中。词法分析器存储两种重要的属性,一个是符号的语义,另一个是构成语义的标记类型(例如,字符是一个标识符还是一个操作符)。

    这里介绍的例子是一个非常简单的词法分析器,它分析字符串中的字符,然后将字符分为两组不同类型的标记:一种只包含数字;另一种包含除了数字之外的字符。为了方便起见,假设标记由输入流中的一个空格分开。词法分析器用一个函数lex来实现,当需要产生标记时,lex就会调用解释器。

    该函数首先调用next_token函数(这里没有列出此函数的实现方法)来从输入流istream中获取下一个空格分割的字符串。如果next_token为NULL,那么说明输入流中没有标记了。在这种情况下,该函数返回lexit来告诉解释器没有标记需要处理了。如果next_token找到一个字符串,那么将会执行一些简单的分析来确定字符串表示哪个标记。接下来,该函数会将包含语义和标记类型的结构Symbol插入符号表symtbl中,然后把标记类型返回给解释器。Symbol类型在symbol.h中定义,在该例子中并没有列举出来。

    链式哈希表是一种用来实现符号表的好方法,因为除了它能高效地存放和检索信息之外,事实上它还能用来存储无限量的数据。对编译器来说这一点非常重要,因为在词法分析完成之前我们并不知道程序会包含多少个符号。

    在next_token的运行时间为常量级时,lex的时间复杂度为O(1)。因为,lex只是简单地调用复杂度为O(1)的函数chtbl_insert。

    // 词法分析器的头文件
    
    /* lex.h */
    
    #ifndef LEX_H
    #define LEX_H
    
    #include "chtbl.h"
    
    /* Define the token types recognized by the lexical analyzer. */
    typedef enum Token_ {lexit, error, digit, other} Token;
    
    /* Public Interface */
    Token lex(const char *istream, CHTbl *symbol);
    
    #endif // LEX_H

    // 词法分析器的实现
    
    /* lex.c */
    
    #include <ctype.h>
    #include <stdlib.h>
    #include <string.h>
    
    #include "chtbl.h"
    #include "lex.h"
    #include "symbol.h"
    
    /* lex */
    Token lex(const char *istream, CHTbl *symtbl)
    {
    	Token token;
    	Symbol *symbol;
    	int length, retval, i;
    
    	/* Allocate space for a symbol. */
    	if((symbol = (Symbol *)malloc(sizeof(Symbol))) == NULL)
    		return error;
    
    	/* Process the next token. */
    	if((symbol->lexeme = next_token(istream)) == NULL)
    	{
    		/* Return that there is no more input. */
    		free(symbol);
    		return lexit;
    	}
    	else
    	{
    		/* Determine the token type. */
    		symbol->token = digit;
    		length = strlen(symbol->lexeme);
    
    		for(i = 0; i < length; i++)
    		{
    			if(!isdigit(symbol->lexeme[i]))
    				symbol->token = other;
    		}
    
    		memcpy(&token, &symbol->token, sizeof(Token));
    
    		/* Insert the symbol into the symbol table. */
    		if((retval = chtbl_insert(symtbl, symbol)) < 0)
    		{
    			free(symbol);
    			return error;
    		}
    		else if(retval == 1)
    		{
    			/* The symbol is already in the symbol table. */
    			free(symbol);
    		}
    	}
    
    	/* Return the token for the parser. */
    	return token;
    }

    注:上述代码仅供理解,无法运行。


    5、开地址哈希表的描述

    在链式哈希表中,元素存放在每个地址的"桶"中。而在开地址哈希表中,元素存放在表本身中。这种特性对于某些依赖于固定大小表的应用来说非常有用。然而,因为在每个槽位上没有一个"桶"来存储冲突元素,所以开地址哈希表需要通过另一种方法来解决冲突。

    冲突解决

    鉴于链式哈希表自身就有能够解决冲突的机制,开地址哈希表必须以一种不同的方式来解决冲突。在开地址哈希表中解决冲突的方法就是探查这个表,直到找到一个可以放置元素的槽。例如,如果要插入一个元素,我们探查槽位直到找到一个空槽,然后将元素插入到此槽中。如果要删除或者找一个元素,我们探查槽位直到定位到该元素或直到找到一个空槽。如果在找到元素之前找到一个空槽或遍历完所有槽位,那么说明此元素在表中不存在。

    当然,在进行操作时要尽可能地减少探查的次数。究竟进行过多少次探查后就停止探查主要取决于两件事:哈希表的负载因子和元素均匀分布的程度。回想一下,哈希表的负载因子α=n/m,其中n为元素的个数,m为可以散列元素的槽位的个数。要注意,根据开地址哈希表的定义,它所包含的元素不可能大于表中槽位的数量,所以开地址哈希表的负载因子通常小于或等于1。这是显而易见的,因为每个槽至多能够容纳一个元素。

    假设进行均匀散列,我们能够在一个开地址哈希表中探查的槽位个数是:

    1/(1-α)

    例如,对于一个处于半满状态的开地址哈希表来说(负载系数为0.5),我们期望能够探查的槽位个数为1/(1-0.5)=2。下表显示了当哈希表的负载因子趋近于1(或100%,即表完全满)时,我们期望探查的槽位数量如何显著增大的。在一个对时间特别敏感的应用中,就可以通过增加哈希表的空间来提高探查的效率。

    假设是均匀散列,期望探查次数变化随负载因子变化的规律
    负载因子(%) 期望探查次数
    <50 <1/(1-0.50)=2
    80 1/(1-0.80)=5
    90 1/(1-0.90)=10
    95 1/(1-0.95)=20







    哈希表的性能是否能够接近于表中所述的规律取决于我们是否能够近似均匀散列。与链式哈希表一样,这关键取决于如何选择哈希函数。然而,在一个开地址哈希表中,这也取决于当发生冲突时如何探查后续表的槽位。一般来说,在开地址哈希表中探查槽位的哈希函数定义为:

    h(k, i)=x

    其中,k是键,i是到目前为止探查的次数,x是得到的哈希编码。通常情况下,与链式哈希表一样,h会调用一个或多个具有相同属性的辅助哈希函数。但在开地址哈希表中,h必须具有一个额外的哈希属性:当i从0增加到m-1时(m为哈希表中槽位个数),在第二次访问任何槽位之前,表中所有的槽位都必须访问过一遍;否则,就说明不需要探查所有的槽位就能找到结果。

    线性探查

    开地址哈希表中一种简单的探查方法就是探查表中连续的槽位。正式地表述为,如果i大于0小于m-1(m为表中的槽位个数),那么一个线性探查方法的哈希函数定义为:

    h(k, i)=(h'(k) + i) mod m

    函数h'是一个辅助哈希函数,就像任何哈希函数的选择方法一样,它会尽可能地将元素随机和均匀地分布在表中。例如,可以采用取余法,这样h'(k)=k mod m。在这种情况下,如果将一个元素(键k=2998)散列到表(容量m=1000),所得到的哈希编码为(998+0) mod 1000 = 988(当i=0时),(998+1) mod 1000 = 999(当i=1时),(998+2) mod 1000 = 0(当i=2时),依此类推。所以,当要插入一个键k=2998的元素时,我们会寻找一个空的槽位,首先探查槽位998,然后槽位999,然后槽位0,依此类推。

    线性探查的优点就是简单,可以保证所有的槽位最终都可能探查到。遗憾的是,线性探查并不能近似均匀散列。特别是当遇到一种称为基本聚集的情况时,基本聚集会产生很长的探查序列,从而使表变得越来越大。这种过度的探查会降低表的性能(见下图)。

    线性探查

    双散列

    最有效地探查开地址哈希表的方法之一,就是通过计算两个辅助哈希函数哈希编码的和来得到哈希编码。正式地表述为,如果i的大小在0和m之间(m为表中槽位个数),双散列的哈希函数定义为:

    h(k, i) = (h1(k) + i*h2(k)) mod m

    函数h1和h2是两个辅助哈希函数,它们与其他的哈希函数一样,也会尽可能地将元素随机和均匀散列到表中。然而,为了保证第二次访问任何一个槽之前其他所有槽都访问过了,我们必须遵循如下规则:一种方法是,m必须是2次幂,让h2返回一个奇数值;另一种方法是选择m为一个素数,h2返回的值在1≤h2(k)≤m-1之间。

    通常情况下,令h1(k)=k mod m,h2(k)=1+(k mod m'),其中m'略小于m,类似等于m-1或m-2。例如,用这种方法,如果哈希表槽位数m=1699(一个素数),取m'=m-2=1697,要散列的键k=15385,探查到的槽位为(94+0×113) mod 1699 = 94(当i=0时),以及之后的每隔113个位置的槽位(随着i的增加)。

    双散列的优点是,它能够在表中探查并产生较好的元素分布(见下图)。其缺点是,必须限制m的值,这样才能保证在一系列探查中访问表中所有槽之后才会再次探查任何槽。

    双散列


    6、开地址哈希函数的接口定义

    ohtbl_init

    ——————

    int ohtbl_init(OHTbl *htbl, int positions,  int (*h1)(const void *key), int (*h2)(const void *key), int (*match)(const void *key1, const void *key2), void (*destroy)(void *data));

    返回值:如果哈希表初始化成功,返回0;否则返回-1。

    描述:初始化开地址哈希表htbl。在对哈希表进行其他操作之前必须首先调用初始化函数。表中槽位的个数将由positions指定。函数指针h1和h2用来指定用户定义的辅助哈希函数来完成双散列的过程。函数指针match指向一个用户定义的函数,此函数用于判断两个键是否匹配,其使用方法和chtbl_init中的match类似。参数destroy是一个函数指针,通过在ohtbl_destroy中调用destroy指定的函数来释放动态分配的内存空间,同样,它与chtbl_destroy中参数的使用方法类似。如果哈希表中的数据不需要释放,那么destroy应该指向NULL。

    复杂度:O(m),m是哈希表中槽的个数。


    ohtbl_destroy

    ——————

    void ohtbl_destroy(OHTbl *htbl);

    返回值:无

    描述:销毁htbl指定的开地址哈希表。在调用ohtbl_destroy之后不再允许进行其他操作,除非再次调用ohtbl_init。ohtbl_destroy会删除哈希表中的所有元素,并当ohtbl_init中参数destroy不为NULL时,释放成员所占用的内存空间。

    复杂度:O(m),m是哈希表中槽的个数。


    ohtbl_insert

    ——————

    int ohtbl_insert(OHTbl *htbl, const void *data);

    返回值:如果插入元素成功,返回0;如果哈希表中已经包含此元素,返回1;否则,返回-1。

    描述:向htbl指定的开地址哈希表中插入一个元素。新元素包含一个指向data的指针,因此,只要元素仍然存在于哈希表中,此指针就一直有效。与data相关的内存空间将由函数的调用者来管理。

    复杂度:O(1)


    ohtbl_remove

    ——————

    int ohtbl_remove(OHTbl *htbl, void **data);

    返回值:如果删除元素成功,返回0;否则,返回-1。

    描述:从ohtbl指定的开地址哈希表中删除与data匹配的元素。返回时,data指向已删除元素中存储的数据。与data相关的内存空间将由函数的调用者来管理。

    复杂度:O(1)


    ohtbl_lookup

    ——————

    int ohtbl_lookup(const OHTbl *htbl, void **data);

    返回值:如果在表中找到元素,返回0;否则,返回-1。

    描述:查找htbl指定的开地址哈希表中是否有与data相匹配的元素。如果找到,在函数返回时,data将指向哈希表中相匹配元素的数据。

    复杂度:O(1)


    ohtbl_size

    ——————

    int ohtbl_size(const OHTbl *htbl);

    返回值:哈希表中元素的个数。

    描述:获取哈希表元素个数的宏。

    复杂度:O(1)


    7、开地址哈希表的实现与分析

    一个开地址哈希表从本质上来说是由一个数组构成的。结构OHTbl是开地址哈希表的数据结构。这个结构包含8个成员:positions指明哈希表中分配的槽位数目;指针vacated将被初始化为指向一个特殊的地址空间,来指明这个特殊地址上曾经删除一个元素;h1、h2、match、destroy时打包传入ohtbl_init的函数指针;size指明表中现有元素的数量;table是存储元素的数组。

    这里需要讨论一下指针vacated。它的存在主要是用来辅助删除元素。一个开地址哈希表的空槽通常包含一个空指针NULL。然而,当删除一个元素时,不能将删除元素的数据指向NULL。这是由于当查找接下来的元素时,NULL表明此槽位是空的,随之探查过程停止。这样一个或多个元素可能被插入之前删除过元素的槽中,但实际上槽中的元素还存在。

    考虑到这一点,当删除元素时,将哈希表中数据的指针指向vacated成员。vacated的地址就像一个哨兵,用于指明新元素将要插入的槽位。这样当寻找一个元素时,就可以放心地认为NULL意味着停止探查。

    // 开地址哈希表的头文件
    
    /* ohtbl.h */
    
    #ifndef OHTBL_H
    #define OHTBL_H
    
    #include <stdlib.h>
    
    /* Define a structure for open-addressed hash tables. */
    typedef struct OHTbl_
    {
        int positions;
        void *vacated;
    
        int (*h1)(const void *key);
        int (*h2)(const void *key);
        int (*match)(const void *key1, const void *key2);
        void (*destroy)(void *data);
    
        int size;
        void **table;
    } OHTbl;
    
    /* Public Interface */
    int ohtbl_init(OHTbl *htbl, int positions, int (*h1)(const void *key), int (*h2)(const void *key), int (*match)(const void *key1, const void *key2), void (*destroy)(void *data));
    
    void ohtbl_destroy(OHTbl *htbl);
    
    int ohtbl_insert(OHTbl *htbl, const void *data);
    
    int ohtbl_remove(OHTbl *htbl, void **data);
    
    int ohtbl_lookup(const OHTbl *htbl, void **data);
    
    #define ohtbl_size(htbl) ((htbl)->size)
    
    #endif // OHTBL_H
    

    // 开地址哈希表抽象数据类型的实现
    
    /* ohtbl.c */
    
    #include <stdlib.h>
    #include <string.h>
    
    #include "ohtbl.h"
    
    /* Reserve a sentinel memory address for vacated elements. */
    static char vacated;
    
    /* ohtbl_init */
    int ohtbl_init(OHTbl *htbl, int positions, int (*h1)(const void *key), int (*h2)(const void *key), int (*match)(const void *key1, const void *key2), void (*destroy)(void *data))
    {
        int i;
    
        /* Allocate space for the hash table. */
        if((htbl->table = (void **)malloc(positions * sizeof(void *))) == NULL)
            return -1;
    
        /* Initialize each position. */
        htbl->positions = positions;
        for(i = 0; i < htbl->positions; i++)
            htbl->table[i] = NULL;
    
        /* Set the vacated member to the sentinel memory address reserved for this. */
        htbl->vacated = vacated;
    
        /* Encapsulate the functions. */
        htbl->h1 = h1;
        htbl->h2 = h2;
        htbl->match = match;
        htbl->destroy = destroy;
    
        /* Initialize the number of elements in the table. */
        htbl->size = 0;
    
        return 0;
    }
    
    /* ohtbl_destroy */
    void ohtbl_destroy(OHTbl *htbl)
    {
        int i;
    
        if(htbl->destroy != NULL)
        {
            /* Call a user-defined function to free dynamically allocated data. */
            for(i = 0; i < htbl->positions; i++)
            {
                if(htbl->table[i] != NULL && htbl->table[i] != htbl->vacated)
                    htbl->destroy(htbl->table[i]);
            }
        }
    
        /* Free the storage allocated for the hash table. */
        free(htbl->table);
    
        /* No operations are allowed now, but clear the structure as a precaution. */
        memset(htbl, 0, sizeof(OHTbl));
    
        return;
    }
    
    /* ohtbl_insert */
    int ohtbl_insert(OHTbl *htbl, const void *data)
    {
        void *temp;
        int position, i;
    
        /* Do not exceed the number of positions in the table. */
        if(htbl->size == htbl->positions)
            return -1;
    
        /* Do nothing if the data is already in the table. */
        temp = (void *)data;
        if(ohtbl_lookup(htbl, &temp) == 0)
            return 1;
    
        /* Use double hashing to hash the key. */
        for(i = 0; i < htbl->positions; i++)
        {
            position = (htbl->h1(data) + (i * htbl->h2(data))) % htbl->positions;
    
            if(htbl->table[position] == NULL || htbl->table[position] == htbl->vacated)
            {
                /* Insert the data into the table. */
                htbl->table[position] = (void *)data;
                htbl->size++;
                return 0;
            }
        }
    
        /* Return that the hash functions were selected incorrectly. */
        return -1;
    }
    
    /* ohtbl_remove */
    int ohtbl_remove(OHTbl *htbl, void **data)
    {
        int position, i;
    
        /* Use double hashing to hash the key. */
        for(i = 0; i < htbl->positions; i++)
        {
            position = (htbl->h1(*data) + (i * htbl->h2(*data))) % htbl->positions;
    
            if(htbl->table[position] == NULL)
            {
                /* Return that the data was not found. */
                return -1;
            }
            else if(htbl->table[position] == htbl->vacated)
            {
                /* Search beyond vacated positions. */
                continue;
            }
            else if(htbl->match(htbl->table[position], *data))
            {
                /* Pass back the data from the table. */
                *data = htbl->table[position];
                htbl->table[position] = htbl->vacated;
                htbl->size--;
                return 0;
            }
        }
    
        /* Return that the data was not found. */
        return -1;
    }
    
    /* ohtbl_lookup */
    int ohtbl_lookup(const OHTbl *htbl, void **data)
    {
        int position, i;
    
        /* Use double hashing to hash the key. */
        for(i = 0; i < htbl->positions; i++)
        {
            position = (htbl->h1(*data) + (i * htbl->h2(*data))) % htbl->positions;
    
            if(htbl->table[position] == NULL)
            {
                /* Return that the data was not found. */
                return -1;
            }
            else if(htbl->match(htbl->table[position], *data))
            {
                /* Pass back the data from the table. */
                *data = htbl->table[position];
                return 0;
            }
        }
    
        /* Return that the data was not found. */
        return -1;
    }
    


    ohtbl_init

    开地址哈希表由ohtbl_init初始化,经过初始化的哈希表才能进行其他操作。开地址哈希表的初始化过程比较简单,其中包括:为表分配空间;将每个槽的指针设置为NULL;封装h1、h2、match和destroy函数;初始化vacated,将它指向标志位地址;最后将size值置0。

    ohtbl_init的时间复杂度为O(m),其中m是表中槽的个数。这是由于m个指向槽中数据的指针都必须初始化为NULL。而剩下的初始化操作都能在固定时间内完成。


    ohtbl_destroy

    开地址哈希表由ohtbl_destroy进行销毁。该函数的主要功能是释放由ohtbl_init分配的内存空间。如果传递给函数ohtbl_init的参数destroy不为NULL的话,每当移除一个元素时,都要调用一次由destroy所指向的析构函数。

    ohtbl_destroy的时间复杂度为O(m),其中m是表中槽的个数。这是由于我们必须遍历哈希表中的所有的槽来判定哪个槽已占用。如果destroy指向NULL,那么ohtbl_destroy的复杂度为O(1)。


    ohtbl_insert

    开地址哈希表由ohtbl_insert向表中插入元素。因为开地址哈希表有固定的大小,所以在插入新元素之前必须保证有足够的空间来放置元素。而且,因为有相同的键不允许重复插入表中,所以在插入新元素时调用ohtbl_lookup来确保表中没有相同的元素存在。

    一旦以上条件得到满足,就可以通过双散列法在表中寻找未占用的槽。如果一个槽的数据指向NULL或槽地址在vacated中(vacated是哈希表中特殊的数据结构,用来记录曾经删除过元素的槽地址),那么说明此槽是一个空槽。一旦在表中找到一个空槽,就将槽的指针指向待插入的数据。如果整个插入过程成功,就将表的容量增大。

    考虑到我们尽量遵从了均匀散列的方法,而且哈希表的负载因子相对较小,ohtbl_insert的时间复杂度为O(1)。这是因为,为了找到一个能够插入元素的空槽,我们可能会探查1/(1-α)个槽,这是一个很小的常量。其中,α是哈希表的负载因子。


    ohtbl_remove

    开地址哈希表通过ohtbl_remove删除表中的元素。为了删除元素,我们像在ohtbl_insert中一样通过双散列法来定位要删除的元素,直到找到这个元素或查找到NULL。如果找到元素,将data指向正在删除的数据,然后将表的大小减1。同时,将槽在哈希表中的地址放到数据结构vacated中。

    考虑到我们尽量遵从了均匀散列的方法,ohtbl_remove的时间复杂度为O(1)。这是因为,为了找到删除元素的槽位,我们会探查1/(1-α)个槽(其中α是自从调用ohtbl_init以来哈希表的最大负载因子),这个常数值很小。为什么删除操作的性能由最大负载因子决定,而且不会随着删除元素而减少,是因为我们仍然会去探查曾经删除过元素的槽。


    ohtbl_lookup

    开地址哈希表通过ohtbl_lookup查找元素,并返回一个指向查找到的数据的指针。此操作与ohtbl_remove非常类似,只是在查找到元素后它不会执行删除操作。

    考虑到我们尽量遵从了均匀散列的方法,ohtbl_lookup的时间复杂度为O(1)。其原因与ohtbl_remove操作相同。这是因为我们希望探查1/(1-α)个槽位,这是一个很小的常数,其中α是自从调用ohtbl_init以来哈希表的最大负载因子。性能依赖于最大负载因子的原因同ohtbl_remove中一样。


    ohtbl_size

    获取开地址哈希表的元素数量的宏定义。它通过结构OHTbl的成员size来获取元素个数。

    其时间复杂度为O(1)。因为获取过程是一个常量级别运算过程。



    展开全文
  • 哈希索引

    千次阅读 2019-05-22 17:09:45
    哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),哈希码是一个较小的值,并且不同键值的行计算出来的哈希码...

    哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),哈希码是一个较小的值,并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针。

    哈希索引可细分为静态哈希和动态哈希这两大类,先介绍静态哈希,然后再介绍动态哈希。

    静态哈希

    基于散列技术的文件组织使我们能够避免访问索引结构,同时也提供了一种构造索引的方法。在对散列的描述中,使用桶(bucket)来表示能存储一条或多条记录的一个存储单位。通常一个桶就是一个磁盘块,但也可能大于或者小于一个磁盘块。

    散列索引将散列函数作用于搜索码以确定对应的桶, 然后将此搜索码以及对应的指针存入此桶(或溢出桶)中。

    静态哈希.png

    【散列函数(hash function)】:令 K 表示所有的搜索码值的集合, 令 B 表示所有桶地址的集合,,散列函数 h 是一个从 K 到 B 的函数.。

    • 插入操作:计算 h(Ki),从而获得存放该记录的桶的地址,并将记录存储到该桶中;
    • 查找:计算 h(Ki),然后搜索具有该地址的桶;
    • 删除:计算 h(Ki),然后在相应的桶中查找此记录并从中删除它。

    【散列函数的特点】:

    • 理想的散列函数把存储的码均匀地分布到所有的桶中,使每个桶含有相同数目的记录。
    • 分布是均匀的:即散列函数从所有可能的搜索码值集合中为每个桶分配同样数量的搜索码值。
    • 分布是随机的:即在一般情况下, 不管搜索码值实际怎样分布, 每个桶应分配到的搜索码值数目几乎相同. 更确切地说, 散列值不应与搜索码的任何外部可见的排序相关, 例如按字母的顺序或按搜索码长度的顺序. 散列函数应该表现为随机的.

    桶溢出

    到目前为止,我们一直假设插入记录时,记录映射到的桶有存储记录的空间。若此时桶已经没有足够的空间,就会发生桶溢出现象。

    【产生原因】:

    • 桶不足:通数目(用 Nb 表示)的选择必须使 Nb > Nr/fr,其中 Nr 表示将要存储的记录总数,fr 表示一个桶能存放的记录数目。需要注意的是,这种表示是以记录总数已知为前提选择散列函数。
    • 偏斜:某些桶分配到的记录比其他桶多,所以即使其他桶仍有空间,某个桶也仍可能溢出,这种情况称为桶偏斜。偏斜发生的原因有两个:
      • 多条记录可能有相同的搜索码;
      • 所选的散列函数可能会造成搜索码的分布不均。

    【处理方案】:溢出链。

    桶的数目选为 (Nr / fr) * (1 + d),其中 d 为避让因子,取值一般约为 0.2。相当于增加了桶的数目(若桶的数目不为整数,则向上取整),虽然有一些空间会浪费,但在一定程度上减少了溢出的可能性。

    需要明确的是:尽管分配的桶比所需的桶多一些,但是桶溢出还是可能发生。我们用溢出桶(多出来的那些桶)来处理桶溢出问题。具体过程如下:如果一条记录必须插入桶 b,而桶 b 此时已满,系统会提供另一个溢出桶来存储该记录。如果溢出桶也满了,再提供另一个溢出桶,如此循环。

    一个给定桶的所有溢出桶用一个链表链接在一起,使用这种链表的溢出处理称为溢出链

    溢出链.png

    为了处理溢出链, 我们需要将查找算法做轻微的改动。和前面一样,系统使用搜索码上的散列函数来确定一个桶 b,系统必须检查桶 b 中所有的记录,看是否有匹配的搜索码。此外,如果桶 b 有溢出桶,则系统还要检查桶 b 的所有溢出桶中的记录。

    静态哈希的缺点

    静态散列最大的缺点在于必须在实现系统时选择确定的散列函数。此后若被索引的文件变大或缩小,要想再改变散列函数就不容易了。因为散列函数 h 将搜索码值映射到桶地址的固定集合 B 上:

    • 根据当前文件大小选择散列函数,这样的选择会使得性能随着数据库的增大而下降。换言之,初始时集合 B 太小,一个桶就会包含许多不同的搜索码值的记录,从而可能发生桶溢出。当文件变大时,性能就会受到影响。
    • 根据将来某个时刻文件的预计大小选择散列函数。 尽管这样可以避免性能下降,但是初始时会造成相当大的空间浪费。

    虽然我们可以随着文件增大,周期性地对散列结构进行重组。这种重组涉及一系列问题:

    • 包括新散列函数的选择;
    • 在文件中每条记录上重新计算散列函数;
    • 分配新的桶。

    重组是一个规模大、耗时的操作,而且重组期间必须禁止对文件的访问。所以我们需要解决的问题就是如何动态地改变桶的数目和散列函数。

    动态哈希

    针对静态散列技术出现的问题,动态散列(dynamic hashing)技术允许散列函数动态改变,以适应数据库增大或缩小的需要,下面介绍可扩充散列(extendable hashing)。

    可扩充散列

    当数据库增大或缩小时,可扩充散列可以通过桶的分裂或合并来适应数据库大小的变化,这样可以保持空间的使用效率。此外,由于重组每次仅作用于一个桶,因此所带来的性能开销较低。

    【做法】:

    • 选择一个具有均匀性和随机性特性的散列函数 h。此散列函数产生的值范围相对较大,是 b 位二进制整数,一个典型的 b 值是 32。
    • 把记录插入文件时按需建桶,用小于等于 b 的 i 个位用作附加桶地址表中的偏移量,i 的值会随着数据库大小的变化而增大或者减少。

    可扩充散列.png

    查询操作

    【过程】:查找包含搜索关键字 k 的存储桶。

    1. 计算 h(k) = X;
    2. 使用 X 的前 i 个高位作为存储区地址表的偏移量,并按指针指向相应的存储区。

    插入操作

    【过程】:插入具有搜索关键字 k 的记录。

    1. 按照查询操作找到存储桶,假设定位到桶编号为 j。如果该存储桶仍然有空间,则在该存储桶中插入记录,否则必须拆分存储桶,并将该桶中现有记录和新记录一起进行重新分配。为了拆分该存储桶,系统必须先根据散列值确定是否需要增加所使用的位数。
    2. 然后根据 i(global depth)和 ij(local depth)的大小关系进行相应的操作。
      • 如果 i = ij,那么在桶地址表中只有一个指向桶 j 的指针,所以系统需要增加桶地址表的大小。以容纳由于桶 j 分裂而产生的两个桶指针。为了达到这个目的,系统可以将 i 的值加 1,从而使桶地址表的大小加倍。这样,原表中每个表项都被两个表项替代,两个表项都包含和原表项一样的指针。现在桶地址表中有两个表项指向桶 j。系统重新分配一个桶(桶z),并让第二个表项指向此新桶。桶 j 中的各条记录重新散列, 根据前 i 位(i 已经加1)来确定该记录是放在桶 j 中还是放在新创建的桶中。
      • 如果 i > ij,那么就有多个表项(指针) 指向桶 j。因此,不需要扩大桶地址表就可以分裂桶 j。指向桶 j 的所有表项的索引前缀的最左 ij 位相同。系统分配一个新桶(桶 z),将 ij 和 iz 置为原 ij 加 1 后得到的值。然后系统需要调整桶地址表中原来指向桶 j 的表项。系统让这些表项的前一半保持原样(指向桶 j),而后一半指向新创建的桶 (桶 z)。然后桶 j 中的各条记录重新被散列,分配到桶 j 或者桶 z 中。

    【示例】:假设现在有如下三条搜索码值,h(k1) = 100100,h(k2) = 000110,h(k3) = 110110。先假设桶的大小为 1,并插入前两项 k1 和 k2,可以通过最左边的位值进行区分,得到如下图所示的结果。

    可扩充散列插入操作图示1.png

    接着,插入第三项,此时左边第一位已经无法区分了,所以将 i 增加 1,此时刚好可以将三个搜索码进行区分,见下图。

    可扩充散列插入操作图示2.png

    k1 和 k3 可通过 10 和 11 进行区分,以 0 作为第一位的不需要进行比较,所以 00 和 01 都是指向 k2。

    现在需要插入一条新的搜索码值 h(k4) = 011110。前两位为 01 指向了桶 A,但桶 A 已满,所以需要进行分裂。因为没有更多的搜索码指向桶 A,所以 i 不需要增加,属于 i > ij 的情况,仅需要将桶 A 进行分裂,令 ij + 1,并重新进行分配。

    可扩充散列插入操作图示3.png

    如果,h(k2) = 010110,也就是说 k2 和 k4 都指向桶 D,并且桶 D 已满,更多的搜索码指向桶 D,属于 i = ij 的情况,所以需要将 i 加 1,用左边的三位来作为桶地址。现在将桶 D 分裂,变成 D’ 和 E,并重新进行散列操作,将 k2 放到 D’ 桶中,k4 放到 E 桶中。

    可扩充散列插入操作图示4.png

    删除操作

    【过程】:删除一条搜索码值为 k 的记录。

    系统先查找到对应的桶,设为桶 j。系统不仅要把搜索码从桶中删除,还要把记录从文件中删除。如果这时桶为空了,那么也要将桶删除掉。

    需要注意的是,此时某些桶可能合并(就是与具有相同 ij 值和相同 ij -1 前缀的桶合并),桶地址表的大小也可以减半。


    通过上述分析可总结出动态散列的优缺点。

    【优点】:

    • 随着记录的增加, 动态散列的性能并不会下降;
    • 动态散列有着最小的空间开销。

    【缺点】:

    • 会增加一次额外的查询定位, 因为在查询桶本身之前还需要查找目录来定位桶;
    • 存储区地址表本身可能变得很大;
    • 更改存储区地址表的大小是一项代价昂贵的操作。

    比较分析

    顺序索引和散列索引的比较分析

    【散列索引】:

    • 在数据库中查找一个值的效率更高;
    • 没有办法利用索引完成排序;
    • 在有大量重复值的时候,散列索引的效率也是极低的,因为存在哈希碰撞的情况。

    【顺序索引】:在指出了一个值范围的查询中比散列索引更可取。

    如果存储的数据重复度很低(也就是说基数很大),对该列数据以等值查询为主,没有范围查询、没有排序的时候,特别适合采用散列索引;大多数情况下,会有范围查询,排序、分组等查询特征,就用顺序索引。

    B+ 树索引和哈希索引的比较分析

    【B+ 树】:

    • 所有的值都是按照顺序存储的,并且每一个叶子页到根的距离相同;
    • 适用于全键值、键值范围或者键前缀查找。顺序索引技术在指出了一个值范围的查询中比散列索引更可取。

    【哈希索引】:基于哈希表实现,只有精确匹配索引所有列的查询才有效。

    • 索引自身只需要存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快。
    • 缺点:
      • Hash索引能使用范围查询;
      • 数据库无法利用Hash索引的数据来避免任何排序运算;
      • Hash索引任何时候都不能避免表扫描。

    Q&A

    问:顺序索引与散列索引的适用场景?

    这两种索引结构都有其优缺点,如果是 select * from a where b=c 这样的定值查询,散列比顺序索引跟适合,顺序索引会随着记录数的增加而性能降低,散列则相对稳定。而对于 where b > c and b < d 这样的范围搜索,则顺序索引更适合,散列的随机特性使得无法定位搜索的桶。所以散列只适合根据搜索码搜索且不是范围查询的场合。

    问:可扩充散列为什么需要局部深度和全局深度?

    可扩展散列允许目录的大小增加或减少,具体取决于插入和删除的数量和种类。

    目录大小更改后,应用于搜索键值的哈希函数也应更改。 因此索引中应该有一些关于要应用哪个哈希函数的信息。 此信息由全局深度提供。

    目录大小的增加不会导致为每个新目录条目创建新存储桶。 每当要拆分由两个或多个目录条目共享的存储桶时,目录大小不需要加倍。这意味着对于每个存储桶,我们需要知道它是由两个或多个目录条目共享。 此信息由存储桶的局部深度提供。(目录:桶地址表)

    总结

    哈希索引思维导图.png

    参考

    展开全文
  • 本文暂且不表这些基础知识,更多的重点在于哈希的一些应用和题目,对于哈希表、哈希函数从来没有学习过或者已经遗忘大部分的同学,建议先去阅读相关内容,否则本文不会成为一篇值得阅读的内容。 1.哈希的函数的定义...

    0.概述

    哈希,或者说散列,在教科书上写的都比较详细,通常包括的内容有散列的方法,散列冲突的解决等。本文暂且不表这些基础知识,更多的重点在于哈希的一些应用和题目,对于哈希表、哈希函数从来没有学习过或者已经遗忘大部分的同学,建议先去阅读相关内容,否则本文不会成为一篇值得阅读的内容。

    1.哈希的函数的定义以及性质

    之所以要介绍这一小节,主要是几乎所有的哈希函数的应用都离不开定义和性质,也正是因为哈希函数拥有这些性质才在各种场景发挥着优秀的性能。

    定义:

    • out = f(in),其中输入域为无穷,值域为有限域。

    哈希函数的定义就是这么简单,就是一个函数,将无限域的输入值映射到有限域的一个函数,具体的这个函数是什么,其实并不是固定的,但是也不是随意的,但是只要能够符合以下的几个性质,并且能够有效地运用到具体的实际当中就可以称作哈希函数,比较著名的哈希函数有MD5,SHA1等密码领域的算法。

    性质:

    • 输入域有限,输出域无限;
    • 无随机性,同一输入一定有相同的输出,但是不同的输入也可能有相同的输出;
    • 强离散性,相似的输入经过散列函数后得到的结果大相径庭;
    • 均匀性,对于输入经过散列函数后得到的结果等概率分布在输出域上;

    简单的理解一下这几个性质,所谓的无随机性是很好理解的,因为根据定义我们知道输入域是大于输出域的,所以不同的输入是可能散列到同一结果的。关于离散性和均匀性其实说的是同一个事儿,原输入可以被均匀的充分的打乱,也就是散列结果的疏密是比较均匀的,这样的好处也是显而易见的,我们肯定不希望申请的存放输出的空间得到浪费,另外即使第二条说不同输入可能映射到相同的输出,我们也不希望结果密集的存放在相同的几个索引上吧,否则哈希表的数据结构查起来是相当没有效率的。

    2.哈希表的扩容和复杂度

    同样的,这里也不会详细解释什么是哈希表,关于哈希表的数据结构还是很重要的,目前在java工程师面试中,HashMap几乎是人人都会的知识点了,关于HashMap的介绍博主本人写了两篇相关的长篇幅:深入理解HashMap(一)深入理解HashMap(二)。感兴趣的读者可以研读,其中比较详细的介绍了java中哈希表的使用和数据结构的实现。

    如果你了解哈希表,一定知道出现哈希冲突的时候,是在相同的索引向后挂节点的(比如链表)。但是由于随着数据的变多,链表节点越挂越多,性能变低,所以关于哈希表有一套扩容机制,但是这个扩容机制各个语言有着不同的实现,比如我写的深入理解HashMap(一)中就介绍了hashmap的扩容机制。我们这里把问题简单化,我们就用最简单的扩容方法,就是将哈希表*2,比如原本申请的key值数组长度为8,下表索引为0~7,扩容后索引变为0~15,由于哈希表长度变化,所以要重新计算哈希值,这样链表长度也就能减少一半(散列性、均匀性)。教科书上一般都写的是哈希表的CRUD时间复杂度为O(1),在不扩容的情况下,确实如此,因为哈希表数据结构的物理存储结构只有两种:顺序存储结构和链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组。比如我们要新增或查找某个元素,我们通过把当前元素的关键字,通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。但是扩容就需要重新计算哈希值,导致总时间复杂度变为多少呢,是O(N*logN),单次时间复杂度就变成\frac{O(N*logN)}{N}  。这很好理解,扩容的次数几乎就是logN,比如说32个数,初始哈希表为2,扩容次数就是log_{2}^{32},每一次扩容重新计算哈希值得代价都是全量N,所以得到总时间复杂度为O(N*logN),对于N个数均摊下来单次的时间复杂度就是\frac{O(N*logN)}{N} 了。

    那么对于使用C++的朋友呢,就是以上默认结果了,但是这是可以优化的,优化成O(1),这个O(1)指的是对于用户来说的,比如说java语言,扩容的时间是被jvm托管的,这个过程是离线完成的,对于用户来说调用的结构一直是一个构建好的哈希表。


    在具体语言中,对于哈希表的实现还是不尽相同的,所以对于刷算法题,通常建议使用java和C++,因为这两种语言纯粹的语法也可以,封装好的api也有。但是对于主流语言中的Python,用过Python的都知道,Python的数组几乎可以干所有的事情,这对于刷题人来说可解释性就没有那么强了。


    3.哈希算法的应用--大文件统计高频数字

    题目:

    有一个大文件,其中存放着40亿个无符号的整数数字,统计出来出现次数最多的数,内存限制1G。

    解析:

    无符号的整数数字取值范围为0~2^{32}-1,故是有可能40亿个数完全不同的。这是最坏的情况,我们假设这种最坏情况,我们定义哈希表为table<int key, int value>,key-value指的是某个数(key)出现的次数(value),也就是一条记录占了8个Byte(字节)的空间,40亿个不同的数字需要8 * 40亿个Byte(字节)空间,也就是32个G,另外哈希表本身的一些信息数据占据了一部分,我们这里就大约认为是32G的空间,但是题目只提供1G的内存,所以创建传统的哈希表肯定是不可取的。这个问题主要是由于数字太多,而且是不同的数字。。

    优化:

    解决方式就是把大文件分成小文件,由于40亿个数是K种数(K最小为一种,最大为40亿种),我们令每个数字经过哈希函数得到的输出再对100取模,这样得到的结果必然是0~99。即:temp = f(in)out = temp%100。
            经过这样的计算,我们就将大文件切分为了100个小文件,把40亿个数字均匀的分到了100个文件中,而且得到的每个文件种数字的种类大致是一样的,这是由哈希函数的均匀性决定的,之所以开篇用了不少篇幅介绍了哈希函数相关的内容,就是为了更好的去理解具体应用,之后还是有很多这样的情况。那么现在我们这40亿个数最差情况是都不相同,也就是有40亿种数字,则每个小文件中大概有4000w个数,1G内存肯定是足够的(其实分成几个文件是由给定内存决定的,这里假设100个是可以的,其实还可以更小一些)。根据哈希函数的性质,同一种数不可能被散列到不同的小文件上,也就是说同一种数一定会落到同一个小文件内。我们用1G内存去统计0号文件中出现次数最多的数,然后释放,再去统计1号文件中的出现次数最多的数字,直到99号文件,最终100个数字词频最高的则返回,就是结果。

    4.设计RandomPool结构

    题目描述:

    • insert(key);不重复插入,即相同的key值只记录一次。
    • delete(key);
    • getRandom();等概率随机返回任一key。

    要求时间复杂度为O(1);

    解析:

    本题还是比较简单的,不重复插入就不介绍了,用图的形式把建好插入的结构展现出来,然后去分析。我们需要建立两张hash表一张是正常的key-value存放,另一张是把第一张表的value当做key,key当做value存,这样做的目的是为了实现getRandom()函数,数据就用26个字母作为操作数据,另外需要一个size变量,初始值为0。

    key value size = 0

    key

    value
    "A" 0 size = 1 0 "A"
    "B" 1 size = 2 "B" 1
    ....... ....... ....... ....... .......
    "Z" 25 size = 26 25 "Z"

     

    getRandom()函数实现使用Math函数库就可以,size值记录了记录条数,所以随机返回0~25中的一个值可以写:

    int index = Math.random(size);
    int reskey = table2.get(index); //table2(HashMap<int, String>)为哈希表2
    String resValue = table1.get(reskey); //table1(HashMap<String, int>)为哈希表1

    本题的坑位出现在delete(key)函数的实现上,因为删除后,索引就不再连续,之后再次调用getRandom()函数的时候,就需要进行进一步的判断,因为哈希表随着插入和删除,不会出现大量的空白索引,Math.random(size)也无法产生等概率的随机数了(准确说是不一定存在),时间复杂度不再是O(1)了,因为当出现不存在的索引,就会再次获取随机数,这样最差情况就是O(N)级别的了,因为最差就是仅剩下一条记录,而且每次获得随机的index都没取到,直到第N次。

    优化:

    删除的时候不是简单的删除,而是从哈希表的索引值末值去取值,用它去覆盖要删除的记录,然后size--。比如要删除"A"-0这条记录,我们去获取"Z"-25,然后覆盖掉"A"-0,变成:

    key value size = 0

    key

    value
    "Z" 0 size = 1 0 "Z"
    "B" 1 size = 2 "B" 1
    ....... ....... ....... ....... .......
    "Y" 24 size = 25 24

    "Y"

     

    5.布隆过滤器

    布隆过滤器是一个只支持从一个集合中检验某个记录是否出现过的过滤器。

    5.1位图

    定义:

    位图就是bit类型的数组,就是以一个位的0-1表示信息。

    示例:

    int[] arr = new int[10];//该整型数组占40个Byte,也就是320bit
    
    /*比如arr[0]表示0~31位置上的状态
     *    arr[1]表示32~63位置上状态
     *依次类推
     */
    
    //取178位的状态
    int numIndex = 178 / 32;  // 178/32得到在数组arr上位于0~10的哪个位置,这里答案是5
    int bitIndex = 178 % 32; // 178%32得到在arr[5]上的160~191比特位置的哪个位置,得到18
    int s = (arr[numIndex] >> bitIndex) & 1; //得到第178位的状态
    
    //把178位的信息改为1
    arr[numIndex] = arr[numIndex] | (1 << bitIndex)
    
    //把178位的信息改为0
    arr[numIndex] = arr[numIndex] & (~(1 << bitIndex))

    5.2黑名单URL问题

    题目描述:

    现在有一个大文件中存放着100亿条URL,每条URL大小为64Byte,如何判断一条URL是否在此文件中出现过。

    分析:

    如果把100亿条URL全部放入HashSet里,100亿*64 = 640G,这需要640G的内存,几乎是不现实的选择,如果存到硬盘中,读取又花费相当长的时间,如何将这100亿条URL记录放到内存当中呢?

    应用:

    布隆过滤器是有常见应用场景的,比如说日常我们使用搜索引擎,如何避免用户搜寻到敏感不健康的链接,如何筛选URL黑名单等。

    解答:

    首先实现一个长度为m的位图,另外我们还需要K个独立的哈希函数,对每一个URL都进行K个哈希函数的计算,得到K个哈希值,这K个哈细值对m进行取模运算,得到需要改变为1状态的bit位置。然后换下一个URL,知道把100亿个URL全部操作完成,布隆过滤器就完成了。下面是个伪代码的实现过程。

    int[] bitArr = new int[m];
    int i = 0;
    //把每一个URL的信息写进布隆过滤器中
    while(url){
    
        //每个URL都进行K个独立的哈希函数的运算,对应K个位置的信息
        while(i < K){
    
            //求该URL在第i个哈希函数下求得需要改变位图位置
            int temp = hashFunction_i(url);
            int res_bit_position = temp % m;
    
            //把在该哈希函数求的的bit位置信息状态改为1
            int numIndex = res_bit_position / 32;
            int bitIndex = res_bit_position % 32;
            bitArr[numIndex] = arr[numIndex] | (1 << bitIndex);
    
            i++;
        }
    
        url++;
    }

    那么现在我们有了布隆过滤器,已经将URL都填进了黑名单中,那么接下来就是如何检测某一个URL是否出现在黑名单当中。依旧是伪代码实现过程如下:

    i = 0;
    int res = 1;
    while(i < K) {
    
        //求url_x在第i个哈希函数下求得需要获取的位图位置
        int temp = hashFunction_i(url_x);
        int res_bit_position = temp % m;
    
        //取url_x在该哈希函数下求得的位置的状态
        int numIndex = res_bit_position / 32;  
        int bitIndex = res_bit_position % 32; 
        s = (arr[numIndex] >> bitIndex) & 1;
     
        //将K次位置的信息进行与操作
        res = s & res;
    }
    
    //如果res为1也就是,每次求得的位置都为1,可以认为该URL在黑名单中,返回true
    return res?true:false;

     以上就是整个布隆过滤器的实现和检测过程,但是读者可能会疑惑,还有两个未知量没有讨论,位图的大小m和K个独立的哈希函数,这两个参数呢放到下一小结5.3中讨论。


    单记录的大小是不影响布隆过滤器的大小的,也就是布隆过滤器大小不跟单样本大小有关,只和样本个数有关。 


    5.3失误率

    由于哈希函数的性质,不同的输入也有可能获得相同的结果,所以布隆过滤器是有一定失误率的,但是这个失误类型的判错是不会判错必为已存在信息的,通俗说就是宁可错杀一千,绝不放过一个。只可能将好人误判为坏人,不会将坏人判成好人的。

    失误率是和上一小节末要讨论的两个参数,位图大小m和哈希函数个数K有关系的。这个很好理解,位图越短,那么位图状态为1的比例就越高,失误率越高;位图太长又很浪费。那么究竟多少合适呢,科学家们已经帮我们算好了,具体推导过程非常复杂,完全没有必要去浪费时间研读,直接记住公式就好了:

    m = -\frac{N*ln^{P}}{(ln^{2})^2}K = ln^{2} * \frac{M}{N}

    P是失误率,还是以URL的例题来说,假设100亿个URL,也就是公式中的N,我们的预期失误率为0.0001,万分之一,那么计算的结果为m的大小为26G,K为13,二者都为向上去整。理论值就是这样的,但是在实际应用中m可以根据实际情况大一点点,这样求得的m,K都要略大于理论值。如此一来,实际失误率也会比预期的失误率更小,我们也可以反推求得实际的失误率为:

    P_{real} = (1-e^{-\frac{n*K}{m} })^K

    下面两张坐标图简单直观地表明了P m K之间的关系。

    6.在分布式存储中运用的一致性哈希原理

    当下大数据的火热使得HDFS应用广泛,而分布式数据存储中就用了哈希算法,这里重点说为何要使用一致性哈希。

    最原始的分布式数据库大概长下面这个样子:

    底层的数据服务器实际含有三台,逻辑服务器统一封装,对外表现为一个数据库入口,当新来一条record的时候,该record进行哈希运算,结果对3取模,得到的结果就是要存入哪台物理数据服务器的编号。这样做不仅分担了数据库的压力,而且由于哈希函数的离散性的性质,三台数据库服务器都将负载均衡。在工程上,hashkey的选择是有讲究的,是专门用来计算哈希值的输入,种类最好是多一些,这样对于操作频率存在差异的数据,就可以做到负载均衡。比如对比姓名和国家,姓名就很适合作为hash key,而国家就不合适,因为姓名种类很多,重名很小,但是对于国家,种类较少,能够经常上热搜榜的,用来被搜索和查询的国家数量就更少了,这样就很容易对某一台或某几台数据服务器造成很大的负担,而对冷门的国家名称所在的服务器来说,又是性能过剩的。

    以上是最传统最原始的分布式数据存储,那么它有什么缺点呢?缺点就是,一旦数据服务器需要扩增,则原来计比如说上图三台变成四台,那么最初计算的服务器编号选择就失效了,此时应该是对4进行求模,这样一来,扩增数据服务器的代价就很高了,数据迁移将耗费大量的时间,毕竟要全部重新计算哈希值,重新选择存放的数据库服务器。那么如何解决呢,就是本节要讨论的一致性哈希原理。

    我们考虑把三台服务器在逻辑上看作在一个环上,具体的操作呢,我们可以把每台机器的hostname作为hash key,计算出来哈希值,然后将这个哈希值再次进行哈希,得到环上对应的位置。

    现在我们尝试插入一条记录record:(zhangsan,25),张三25岁这个记录,我们假设以姓名作为hash key计算此条记录的哈希值value,将此条记录存在value在环的顺时针方向上最近的机器上。那么为何这样可以避免前面提到的传统分布式数据库的数据迁移代价呢?我们来看看扩增一台数据服务器是什么样的,假设m4计算之后位于m2和m3之间:

    回顾刚提到的插入一条记录的过程,是不是扩增后m3的数据就其实不一定是存在m3上了,加入数据条目计算的value位于m2和m4之间,那么就应该保存在m4上,但是m1和m2呢,并不会被影响,所以也就是原本由m3负责的数据,部分需要迁移到m4上,而与m1,m2完全无关,这样就不需要全量迁移了,大大提高了效率。


     用户面对的是逻辑服务器层,并不知道真实的物理服务器的情况,那么如何顺时针找到是哪台物理数据库服务器呢?其实就是让machine hash code进行排序,这个就是服务器计算应该在环的那个位置的那个值,把所有的值进行排序,这个序列就是顺时针机器的排列顺序,我们让所有的逻辑服务器都备份一份这个序列,也就可以让数据顺时针对应找到应该在的位置了。


    缺点:

    1. 机器数量很少时,哈希环不一定平分;
    2. 即便初始哈希环上的机器状态为平分哈希环,扩充后也就不再平衡了;

    解决:

    使用虚拟节点技术,还是三台物理数据服务器的例子,我们给每个机器分配1000个字符串,看作是1000个虚拟节点。

    我们让虚拟节点去枪环,3000个值很交错的分布在哈希环上,这样当一条record插入时,顺时针找到最近的虚拟节点进行插入,但是实际选择的是该虚拟节点对应的物理服务器,比如我们在换上选择了b666这个虚拟节点,实际上这条记录是存在了m2中、这样做的好处不仅在增减服务器时不会出现刚才提到的物理机在哈希环上分布不均匀的情况,而且这样负载也比较均衡。进一步地,通过虚拟节点技术还可以做负载管理得 工作,比如m1机器性能好一些,那么我们就给m1多分配一些字符串,如此一来哈希环上属于m1的虚拟节点就占了更多的位置,m1自然也就分担了更多的负载,可以充分发挥m1性能好的优势。

    总结

    哈希函数和哈希表其实原理容易懂,但是还是挺难得,希望本篇文章能让你觉得和详细介绍哈希的基础知识的文章收获不同,个人水平有限,如有错误欢迎指正。

    展开全文
  • 哈希算法

    2020-08-17 15:01:34
    哈希算法的目的就是为了验证原始数据是否被篡改。 Java字符串的hashCode()就是一个哈希算法,它的输入是任意字符串,输出是固定的4字节int整数: "hello".hashCode(); //0x5e918d2 "hello, java".hashCode(); //...

    哈希算法(Hash)又称摘要算法(Digest),它的作用是:对任意一组输入数据进行计算,得到一个对固定长度额输出摘要。

    哈希算法最重要的特点就是:

    • 相同的输入一定得到相同的输出;
    • 不同的输入大概率得到不同的输出。

    哈希算法的目的就是为了验证原始数据是否被篡改。

    Java字符串的hashCode()就是一个哈希算法,它的输入是任意字符串,输出是固定的4字节int整数:

    "hello".hashCode(); //0x5e918d2

    "hello, java".hashCode(); //0x7a9d88e8

    "hello, bob".hashCode(); //0xa0dbae2f

    两个相同的字符串永远会计算出相同的hashCode,否则基于hashCode定位的HashMap就无法正常工作。这也是为什么当我们自定义一个class时,覆写equals()方法时我们必须正确覆写hashCode()方法。

    哈希碰撞

    哈希碰撞是指,两个不同的输入得到了相同的输出:

    "AaAaAa".hashCode();  //0x7460e8c0

    "BBAaBB".hashCode(); //0x7460e8c0

    有童鞋会问:碰撞能不能避免?答案是不能。碰撞是一定会出现的,因为输出的字节长度是固定的,String的hashCode()输出是4字节整数,最多只有4294967296种输出,但输入的数据长度是不固定的,有无数种输入。所以,哈希算法是把一个无线的输入集合映射到一个有限的输出集合,必然会产生碰撞。

    碰撞不可怕,我们担心的不是碰撞,而是碰撞的概率,因为碰撞概率的高低关系到哈希算法的安全性。一个安全的哈希算法必须满足:

    • 碰撞概率低;
    • 不能猜测输出。

    不能猜测输出是指,输入的任意一个bit的变化会造成输出完全不同,这样就很难从输出反推输入(只能依靠暴力穷举)。假设一种哈希算法有如下规律:

    hashA("java001") = "123456"

    hashA("java002") = "123457"

    hashA("java003") = "123458"

    那么很容易从输出123459反推输入,这种哈希算法就不安全。安全的哈希算法从输出是看不出任何规律的:

    hashB("java001") = "123456"

    hashB("java002") = "580271"

    hashB("java003") = ???

    常用的哈希算法有:

    算法 输出长度(位) 输出长度(字节)
    MD5 128 bits 16 bytes
    SHA-1 160 bits 20 bytes
    RipeMD-160 160 bits 20 bytes
    SHA-256 256 bits 32 bytes
    SHA-512 512 bits

    64 bytes

    根据碰撞概率,哈希算法的输出长度越长,就越难产生碰撞,也就越安全。

    Java标准库提供了常用的哈希算法,并且有一套统一的接口。我们以MD5算法为例,看看如何对输入计算哈希:

    import java.math.BigInteger;
    import java.security.MessageDigest;
    
    public class Main {
        public static void main(String[] args) throws Exception {
            // 创建一个MessageDigest实例:
            MessageDigest md = MessageDigest.getInstance("MD5");
            // 反复调用update输入数据:
            md.update("Hello".getBytes("UTF-8"));
            md.update("World".getBytes("UTF-8"));
            byte[] result = md.digest(); //16 bytes:68e109f0f40ca72a15e05cc22786f8e6
            System.out.println(new BigInteger(1, result).toString(16));
        }
    }
    

     

    使用MessageDigest时,我们首先根据哈希算法获取一个MessageDigest实例,然后,反复调用update(byte[])输入数据。当输入结束后,调用digest()方法获得byte[]数组表示的摘要,最后,把它转换为十六进制的字符串。

    运行上述代码,可以得到输入HelloWorld的MD5是68e109f0f40ca72a15e05cc22786f8e6

    哈希算法的用途

    因为相同的输入永远会得到相同的输出,因此,如果输入被修改了,得到的输出就会不同。

    我们在网站上下载软件的时候,经常看到下载页显示的哈希:

    file-md5

    如何判断下载到本地的软件是最原始的、未经篡改的文件?我们只需要自己计算一下本地文件的哈希值,再与官网公开的哈希值对比,如果相同,说明文件下载正确,否则,说明文件已被篡改。

    哈希算法的另一个重要用途是存储用户口令。如果直接将用户的原始口令存放到数据库中,会产生极大的安全风险:

    • 数据库管理员能够看到用户明文口令;
    • 数据库数据一旦泄露,黑客即可获取用户明文口令。

    不存储用户的原始口令,那么如何对用户进行认证?

    方法是存储用户口令的哈希,例如,MD5.

    在用户输入原始口令后,系统计算用户输入的原始口令的MD5并与数据库存储的MD5对比,如果一致,说明口令正确,否则,口令错误。

    因此,数据库存储用户名和口令的表内容应该像下面这样:

    username password
    bob f30aa7a662c728b7407c54ae6bfd27d1
    alice 25d55ad283aa400af464c76d713c07ad
    tim bed128365216c019988915ed3add75fb

    这样一来,数据库管理员看不到用户的原始口令。即使数据库泄露,黑客也无法拿到用户的原始口令。想要拿到用户的原始口令。想要拿到用户的原始口令,必须用暴力穷举的方法,一个口令一个口令地试,直到某个口令计算的MD5恰好等于指定值。

    使用哈希口令时,还要注意防止彩虹表攻击。

    什么是彩虹表呢?上面讲到了,如果只拿到MD5,从MD5反推明文口令,只能使用暴力穷举的方法。

    然而黑客并不笨,暴力穷举会消耗大量的算力和时间。但是,如果有一个预先计算好的常用口令和它们的MD5的对照表:

    常用口令 MD5
    hello123 f30aa7a662c728b7407c54ae6bfd27d1
    12345678 25d55ad283aa400af464c76d713c07ad
    passw0rd bed128365216c019988915ed3add75fb
    19700101 570da6d5277a646f6552b8832012f5dc
    20201231 6879c0ae9117b50074ce0a0d4c843060

     

    这个表就是彩虹表。如果用户使用了常用口令,黑客从MD5一下就能反差到原始口令:

    bob的MD5: f30aa7a662c728b7407c54ae6bfd27d1,原始口令:hello123

    alice的MD5:25d55ad283aa400af464c76d713c07ad,原始口令:12345678

    tim的MD5:bed128365216c019988915ed3add75fb,原始口令:passw0rd

    这就是为什么不要使用常用密码,以及不要使用生日作为密码的原因。

    即使用户使用了常用口令,我们也可以采取措施来抵御彩虹表攻击,方法是对每个口令额外添加随机数,这个方法称之为加盐(salt):

    digest = md5(salt +inputPassword)

    经过加盐处理的数据库表,内容如下:

    username salt password
    bob H1r0a a5022319ff4c56955e22a74abcc2c210
    alice 7$p2w e5de688c99e961ed6e560b972dab8b6a
    tim z5Sk9 1eee304b92dc0d105904e7ab58fd2f64

     

    加盐的目的在于使黑客的彩虹表失效,即使用户使用常用口令,也无法从MD5反推原始口令。

    SHA-1

    SHA-1也是一种哈希算法,

    它的输出是160 bits,即20字节。SHA-1是由美国国家安全局开发的,SHA算法实际上是一个系列,包括SHA-0(已废弃)、SHA-1、SHA-256、SHA-512等。

    在Java中使用SHA-1,和MD5完全一样,只需要把算法名称改为"SHA-1"

    import java.math.BigInteger;
    import java.security.MessageDigest;
    
    public class Main {
        public static void main(String[] args) throws Exception {
            // 创建一个MessageDigest实例:
            MessageDigest md = MessageDigest.getInstance("SHA-1");
            // 反复调用update输入数据:
            md.update("Hello".getBytes("UTF-8"));
            md.update("World".getBytes("UTF-8"));
            byte[] result = md.digest(); // 20 bytes: db8ac1c259eb89d4a131b253bacfca5f319d54f2
            System.out.println(new BigInteger(1, result).toString(16));
        }
    }

     

    类似的,计算SHA-256,我们需要传入名称"SHA-256",计算SHA-512,我们需要传入名称"SHA-512"。Java标准库支持的所有哈希算法可以在这里查到。

     注意:MD5因为输出长度较短,短时间内破解是可能的,目前已经不推荐使用。

    小结

    哈希算法可用于验证数据完整性,具有防篡改检测的功能;

    常用的哈希算法有MD5、SHA-1等;

    用哈希存储口令时要考虑彩虹表攻击。

     

     

     

    展开全文
  • 哈希表支持一种最有效的检索方法:散列。 从根来上说,一个哈希表包含一个数组,通过特殊的索引值(键)来访问数组中...计算哈希值和在数组中进行索引都只消耗固定的时间,因此哈希表的最大亮点在于它是一种运行时...
  • 一致性哈希表 分布式哈希表If you have programmed before, you are sure to have come across hashing and hash tables. Many developers have used hash tables in one form or another, and beginner developers ...
  • 哈希表概述

    千次阅读 2018-05-22 21:46:50
    一、什么是哈希表? &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键...
  • 哈希相关

    2012-09-16 20:58:05
    google搜索到的头条:散列表(也叫哈希表),是根据关键码值直接进行访问的数据结构,也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散...
  • 哈希表 通过查找关键字不需要比较就可获得需要的记录的存储位置。即存储位置=f(关键字) 这就是一种新的存储技术---散列技术(哈希技术) 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每...
  • 哈希表大总结

    2020-11-26 18:32:09
    哈希表总结 哈希表 记录的存储位置和它的关键字之间建立一确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。 因而查找时,只需根据这个对应关系f找到给定值K的像f(K)。 若结构中存在关键字和K相等...
  • 哈希表支持一种最有效的检索方法:散列。 从根来上说,一个哈希表包含一个数组,通过特殊的索引值(键)来访问数组中...计算哈希值和在数组中进行索引都只消耗固定的时间,因此哈希表的最大亮点在于它是一种运行时...
  • 哈希函数简介

    2013-08-18 12:28:54
    这里把这种对应关系f称为散列函数,又称为哈希(Hash)函数。按这个思想,采用散列技术将记录存在在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表。那么,关键字对应的记录存储位置称为散列地址。 散列...
  • 局部敏感哈希

    千次阅读 2016-01-21 22:47:10
    局部敏感哈希 在检索技术中,索引一直需要研究的核心技术。当下,索引技术主要分为三类:基于树的索引技术(tree-based index)、基于哈希的索引技术(hashing-based index)与基于词的倒排索引(visual words ...
  • 加盐哈希

    2016-03-15 13:33:23
    最好的办法就是对密码进行加盐哈希,这篇文章将介绍它是如何做到这点。 在对密码进行哈希加密的问题上,人们有许多争论和误解,这大概是由于网络上广泛的误传吧。密码哈希是一件非常简单的事情,但是依然有很多人...
  • 整数哈希介绍

    千次阅读 2016-06-07 11:45:22
    为什么要整数哈希 http://www.cnblogs.com/napoleon_liu/archive/2010/12/29/1920839.html  很多时候,可以直接用整数作为键,比如QQ号码,手机号码,但这些号码的分布性不是均匀的(比如高位的变化更少,低位...
  • 分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了。介绍的论文很多,这里做一个入门性质的介绍。  分布式哈希(DHT)  两个key point:每个节点只维护一部分路由;每个节点只存储一部分数据...
  • 数据结构之哈希

    2019-04-09 13:59:34
    什么是哈希哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。 哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:...
  • 什么是哈希算法

    千次阅读 2018-05-07 18:27:19
    哈希函数,又称哈希算法,它通过一个函数,把任意长度的数据转换为一个长度固定的数据串(通常用16进制的字符串表示)。 Hash算法特别的地方在于它是一种单向算法,用户可以通过Hash算法对目标信息生成一段特定长度...
  • 基于哈希函数的签名

    千次阅读 2019-05-13 18:28:28
    (这里当然存在许多例外,但最棒的部分在于,不论 X 属于什么分布,找到 X 的时间成本和暴力搜寻相同。) 抗-次原像攻击 :这和前者有些微的差别。给定输入 X,对于攻击者来说,要找到另一个 X' 使得 H(X)=H(X') ...
  • 哈希的基本操作

    2018-08-30 13:27:54
    哈希 哈希冲突 闭散列 开散列 头文件定义 代码各个功能解析 初始化 插入 查找 删除 完整代码 前言 理想的搜索方式:可以不经过任何比较,一次直接从表中得到要搜索的元素,构造一种结构,通过某种函数使...
  • 哈希函数,哈希表与布隆过滤器2. 设计RandomPool结构3. 一致性哈希4. 并查集结构5. 并查集结构应用【岛问题】 1. 哈希函数,哈希表与布隆过滤器   链接 : ...
  • 分布式哈希(DHT)  两个key point:每个节点只维护一部分路由;每个节点只存储一部分数据。从而实现整个网络中的寻址和存储。 DHT只是一个概念,提出了这样一种网络模型。并且说明它是对分布式存储很有好处的。但...
  • 哈希猫很牛吗

    2021-06-16 16:52:14
    哈希猫(Hashcat)是一款在渗透人员、系统管理员,甚至是网络罪犯和网络...它的优点在于瞬间加密,但如果想暴力破解将函数逆向出来,以目前的计算机算力而言,在我们有生之年几乎是不可能的。(数世咨询:王小云教授的破
  • perl学习笔记——哈希

    2015-07-22 16:58:00
    哈希是一种数据结构,它和数组的相似之处在于可以容难任意多的值并能按需取用,而他和数组的不同在于索引的方式,数组是以数字为索引而哈希则是以名字为索引。 哈希的键是唯一的,哈希的值可以重复。 哈希的应用...
  •  所以,本方法的关键在于选择合适的p,若是p选择的不好,就可能产生 同义词;根据前人经验,若散列表的表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。    ⑥、随机数法 ...
  • 哈希算法(Hash)又称摘要算法(Digest),它的作用是:对任意一...哈希算法的目的就是为了验证原始数据是否被篡改。 Java字符串的hashCode()就是一个哈希算法,它的输入是任意字符串,输出是固定的4字节int整数: ...
  • “分布式哈希”和“一致性哈希”的概念与算法实现  (2011-1-24 04:01:50) 标签: 分类:搜索技术  分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了。介绍的论文很多,这里做一个入门...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,938
精华内容 13,175
关键字:

哈希的目的在于