🪴qql1's digital garden

哈希表 哈希查找

7分钟阅读

1. 适用范围:

1. 适用范围:

  1. 从很多记录中快速的查找某个关键字对应的记录

2. 梗概:

  1. 哈希表是一种特殊的线性存储结构
    1. 关键字存储的地址与关键字的值有关
      1. 由哈希函数计算得来
  2. 哈希函数与存储地址:
    1. 存储位置=f(key)
      1. f为哈希函数
  3. 构造可用的哈希表需要兼备哈希函数和冲突处理方法

3. 相关概念:

1. 同义词与冲突:

具有相同哈希函数值的关键字 这种现象也称为冲突

2. 哈希函数插入与查找的关系:

以查找为主, 即先查找再插入 如果查找失败, 就在查找失败的空位插入记录

3. 键簇:

即开放定址法中, 要取多个di, 这些di统称为键簇

4. 常用的几种哈希函数

  1. 线性哈希函数/直接定址法: 如 f(key)=a*key+b和f(key)=key
  2. 数字分析法: 抽取关键字中的一部分(区别尽可能大)传入哈希函数计算
  3. 平方取中法: 将关键字取平方后取中间若干位数传入哈希函数
  4. 折叠法:
    1. 先要把所有关键字补零到相同位数
    2. 将关键字从左到右分割成位数相等的几部分
    3. 将这几部分求和, 取后几位传入哈希函数
  5. 除留余数法: f(key)=key mod 靠近表长的一个素数(⭐)
  6. 随机数法: f(key)=random(key)
    1. 适用范围: 关键字长度不均匀

1. 选取哈希函数的五个因素:

  1. 计算复杂度
  2. 关键字的长度
  3. 散列表的大小
  4. 关键字的分布情况
  5. 查找记录的频率

5. 处理冲突的几种常用方法

1. 开放定址法:

当产生冲突的时候调用以下公式:下一个地址=(上一个地址+di) MOD 表长 其中di的取值又有多种方法:

  1. 线性探测再散列法: 如di依次取取1,2,3…
    1. 缺点: 会产生堆积问题, 且较为严重
  2. 平方/二次探测再散列法: di取1², 2², 3²…
    1. 特点: 也会产生堆积问题, 但比线性探测轻微一点;
    2. 二次探测所产生的堆积问题也称为二次堆积, 二次聚集
  3. 正负探测再散列法: di=-1,2,-3,-4…
    1. 优点: 可以双向寻找空址
    2. 常搭配二次探测法
  4. 随机取值法: di=randon(i)

2. 再散列/哈希法

如果运算结果产生冲突, 则把上一个地址传入另一个哈希函数, 得到下一个地址

3. 链地址法

一个地址用链表存储多个关键字

4. 公共溢出区法:

把所以冲突的关键字线性存放到一个溢出表中 查找的时候先在基本表中查找, 如果没有, 再到溢出表中顺序查找

6. 在c语言中的实现

1. 线性探测法解决冲突

1.1. 查找:

typedef int KeyType;
#define NULLKEY -32768//设置一个一半用不到的值作为空标记符
#define TABLESIZE 64
typedef struct{
    KeyType key;
}RecordType;
typedef RecordType HashTable[TABLESIZE];
 
int Hash(KeyType key){}
 
int HashSearch(HashTable ht, KeyType key){
    int h0=Hash(key);
    if(ht[h0].key==NULLKEY)return -1;
    else if(ht[h0].key==key)return h0;
    /*这里用线性探测处理冲突*/
    else{
        int hi;
        for(int i=1;i<=TABLESIZE-1;++i){
            hi=(h0+i)%TABLESIZE;
            /*因为是按顺序探测的,如果探测到空,则后面都不是目标*/
            if(ht[hi].key==NULLKEY)return -1;
            else if(ht[hi].key==key)return hi;
        }
        return -1;
    }
}

1.2. 插入

梗概:

  1. 与查找差不多, 只不过是找到空位才插入

7. 在JavaScript/ts中的实现:

1. 相关定义:

type keytype = number;
class record{
    constructor(key:keytype){
        this.key=key;
    }
    key:keytype;
}

2. 线形探测处理冲突:

class Hashtable{
    constructor(tableLen?:number){
        this.table=[];
        this.table.length=tableLen?tableLen:this.defautLen;
        this.MaxPrime=2;
        this.UpdataMaxPrime();
    }
    private defautLen=11;
    table:record[];
    MaxPrime:number;
  
    IsPrime(n:number){
        for(let j=2;j*j<=n;){
            if(n%j==0){
                return false;
            }
            return true;
        }
    }
    UpdataMaxPrime(){
        let i;
        for(i=this.table.length;true;--i){
            if(this.IsPrime(i))
                break;
        }
        if(i>this.MaxPrime)this.MaxPrime=i;
    }
    Hash(key:keytype):number{
        return (3*key)%this.MaxPrime;
    }
    conunt:number=0;
    hashSearch(key:keytype){
        let h0=this.Hash(key);
        if(this.table[h0]==undefined){
            return null;
        }
        else if(this.table[h0].key==key){
            return h0;
        }
        else{
            /*线性探测h0之外的地址*/
            for(let i=1;i<this.table.length;++i){
                let hi=(h0+i)%this.table.length;
                if(this.table[hi]==undefined)return null;
                else if(this.table[hi].key==key)return hi;
            }
            return null;
        }
    }
    hashInsert(rcd:record){
        let h0=this.Hash(rcd.key);
        if(this.table[h0]==undefined)
            this.table[h0]=rcd;
        else{//存在同义字,使用线性探测处理冲突
            for(let di=1;di<this.table.length;++di){
                let hi=(h0+di)%this.table.length;
                if(this.table[hi]==undefined){
                    this.table[hi]=rcd;
                    return true;
                }
            }
            return false;
        }
    }
    CreatHash(records:record[]){
        for(let i=0;i<records.length;++i){
            this.hashInsert(records[i]);
        }
    }
}

关系图谱

反向链接