数据结构温习

[TOC]

哈希表

简介:哈希表(Hash table,散列表),是根据K-V而直接访问的一种数据结构。

 

两种类型的哈希表:

_链式哈希表_,通过每个桶附加链表来解决哈希冲突。

开地址哈希表,通过探查这个表,直到找到一个可以放置元素的槽。具体方法有线性探查、双散列。

 

哈希函数:

1,取余,除整取余。

2,处理字符串的哈希函数,ELFhash算法,通过一系列位操作将键强制转换为整数。

int ELFhash(char*key)
{
    unsigned long h=0;
    while(*key)
    {
        h = (h << 4) + *key++;
        unsigned long g = h & 0xF0000000L;
        if(g)
            h ^= g >> 24;
        h &= ~g;
    }
    return h % MOD;
}

← 大数据常用算法——大数据日知录读书笔记  高性能MYSQL读书笔记 →