精华内容
下载资源
问答
  • 哈希算法原理和实现

    千次阅读 多人点赞 2020-09-13 10:32:32
    哈希算法原理和实现 前言 当我们在编程过程中,往往需要对线性表进行查找操作。在顺序表中查找时,需要从表头开始,依次遍历比较a[i]与key的值是否相等,直到相等才返回索引i;在有序表中查找时,我们经常使用的是二...

    哈希算法原理和实现

    前言

    当我们在编程过程中,往往需要对线性表进行查找操作。在顺序表中查找时,需要从表头开始,依次遍历比较a[i]与key的值是否相等,直到相等才返回索引i;在有序表中查找时,我们经常使用的是二分查找,通过比较key与a[i]的大小来折半查找,直到相等时才返回索引i。最终通过索引找到我们要找的元素。
       但是,这两种方法的效率都依赖于查找中比较的次数。我们有一种想法,能不能不经过比较,而是直接通过关键字key一次得到所要的结果呢?这时,就有了散列表查找(哈希表)。

    1、什么是哈希表

    要说哈希表,我们必须先了解一种新的存储方式—散列技术。
        散列技术是指在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每一个关键字都对应一个存储位置。即:存储位置=f(关键字)。这样,在查找的过程中,只需要通过这个对应关系f 找到给定值key的映射f(key)。只要集合中存在关键字和key相等的记录,则必在存储位置f(key)处。我们把这种对应关系f 称为散列函数或哈希函数。
        按照这个思想,采用散列技术将记录存储在一块连续的存储空间中,这块连续的存储空间称为哈希表。所得的存储地址称为哈希地址或散列地址。

    2、哈希表查找步骤

    ①、存储数据时,将数据存入通过哈希函数计算所得哪那个地址里面。
       ②、查找时,使用同一个哈希函数通过关键字key计算出存储地址,通过该地址即可访问到查找的记录。

    3、哈希冲突

    在理想的情况下,每一个 关键字,通过哈希函数计算出来的地址都是不一样的。但是在实际情况中,我们常常会碰到两个关键字key1≠key2,但是f(key1) = f(key2), 这种现象称为冲突,并把key1和key2称为这个散列函数的同义词。
      冲突的出现会造成查找上的错误,具体解决方法会在后文提到。

    4、哈希函数的构造方法

    (1)原则

    ①、计算简单;
      ②、散列地址分布均匀。

    (2)构造方法

    ①、直接定址法:不常用
        取关键字或关键字的某个线性函数值为哈希地址:
        即:H(key) = key 或 H(key) = a*key+b
        优点:简单,均匀,不会产生冲突;
        缺点:需要实现直到关键字的分布情况,适合查找表比较小且连续的情况。
      
      ②、数字分析法
       数字分析法用于处理关键字是位数比较多的数字,通过抽取关键字的一部分进行操作,计算哈希存储位置的方法。
       例如:关键字是手机号时,众所周知,我们的11位手机号中,前三位是接入号,一般对应不同运营商的子品牌;中间四位是HLR识别号,表示用户号的归属地;最后四位才是真正的用户号,所以我们可以选择后四位成为哈希地址,对其在进行相应操作来减少冲突。
       数字分析法适合处理关键字位数比较大的情况,事先知道关键字的分布且关键字的若干位分布均匀。
       
      ③、平方取中法
       具体方法很简单:先对关键字取平方,然后选取中间几位为哈希地址;取的位数由表长决定,适用于不知道关键字的分布,而位数又不是很大的情况。
      
      ④、折叠法
       将关键字分成位数相同的几部分(最后一部分位数 可以不同),然后求这几部分的叠加和(舍去进位),并按照散列表的表长,取后几位作为哈希地址。
       适用于关键字位数很多,而且关键字每一位上数字分布大致均匀。
      
       ⑤、除留余数法
       此方法为最常用的构造哈希函数方法。对于哈希表长为m的哈希函数公式为:
       f(key) = key mod p (p <= m)
       此方法不仅可以对关键字直接取模,也可以在折叠、平方取中之后再取模。
       所以,本方法的关键在于选择合适的p,若是p选择的不好,就可能产生 同义词;根据前人经验,若散列表的表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。
      
       ⑥、随机数法
       选择一个随机数,取关键字的随机函数值作为他的哈希地址。
       即:f(key) = random (key)
       当关键字的长度不等时,采用这个方法构造哈希函数较为合适。当遇到特殊字符的关键字时,需要将其转换为某种数字。

    (3)、参考因素

    在实际应用过程中,应该视不同的情况采用不同的哈希函数。下列是一些参考因素:
        ①计算哈希地址所需的时间;
        ②关键字的长度;
        ③哈希表的大小;
        ④关键字的分布情况;
        ⑤查找的频率。
       选择哈希函数时,我们应该综合以上因素,选择合适的构建哈希函数的方法。

    5、哈希冲突的解决

    前文提到,哈希冲突不能避免,所以我们需要找到方法来解决它。
       哈希冲突的解决方案主要有四种:开放地址法;再哈希;链地址法;公共溢出区法。

    (1)、开放地址法

    开放地址法就是指:一旦发生了冲突就去寻找下一个空的哈希地址,只要哈希表足够大,空的散列地址总能找到,并将记录存入。
       公式:Hi=(H(*key) + Di) mod m (i = 1,2,3,….,k k<=m-1)
       其中:H(key)为哈希函数;m为哈希表表长;Di为增量序列,有以下3中取法:
         ①Di = 1,2,3,…,m-1, 称为线性探测再散列;
         ②Di = 1²,-1²,2²,-2²,。。。,±k²,(k<= m/2)称为二次探测再散列
         ③Di = 伪随机数序列,称为伪随机数探测再散列。
         例如:在长度为12的哈希表中插入关键字为38的记录:
         这里写图片描述
         从上述线性探测再散列的过程中可以看出一个现象:当表中i、i+1位置上有记录时,下一个哈希地址为i、i+1、i+2的记录都将填入i+3的位置,这种本不是同义词却要争夺同一个地址的现象叫“堆积“。即在处理同义词的冲突过程中又添加了非同义词的冲突;但是,用线探测再散列处理冲突可以保证:只要哈希表未填满,总能找到一个不发生冲突的地方。

    (2)、再哈希法

    公式:Hi = RHi(key) i = 1,2,…,k
         RHi均是不同的哈希函数,意思为:当繁盛冲突时,使用不同的哈希函数计算地址,直到不冲突为止。这种方法不易产生堆积,但是耗费时间。

    (3)、链地址法

    将所有关键字为同义字的记录存储在一个单链表中,我们称这种单链表为同义词子表,散列表中存储同义词子表的头指针。
         如关键字集合为{19,14,23,01,68,20,84,27,55,11,10,79},按哈希函数H(key) = key mod 13;
         这里写图片描述
         链地址法解决了冲突,提供了永远都能找到地址的保证。但是,也带来了查找时需要遍历单链表的性能损耗。

    (4)、公共溢出区法

    即设立两个表:基础表和溢出表。将所有关键字通过哈希函数计算出相应的地址。然后将未发生冲突的关键字放入相应的基础表中,一旦发生冲突,就将其依次放入溢出表中即可。
         在查找时,先用给定值通过哈希函数计算出相应的散列地址后,首先 首先与基本表的相应位置进行比较,如果不相等,再到溢出表中顺序查找。

    6、哈希表查找算法的实现

    首先定义一个散列表的结构以及一些相关的常数。其中,HashTables是散列表结构。结构当中的elem为一个动态数组。

    #define SUCCESS 1
    #define UNSUCCESS 0
    #define HASHSIZE 12    /*定义哈希表长为数组的长度*/
    #define NULLKEY -32768
    {
        int *elem;        /*数组元素存储基址,动态分配数组*/
        int count;        /*当前数据元素的个数*/
    }HashTable;
    int m = 0;            
    123456789
    

    初始化哈希表

    /*初始化哈希表*/
    Status InitHashTable(HashTable *H)
    {
        int i;
        m = HASHSIZE;
        H->count = m;
        H->elem = (int *)malloc(m*sizeof(int));
        for(i = 0;i<m;i++)
            H->elem[i] = NULLKEY;
    
        return OK;
    }   
    123456789101112
    

    定义哈希函数

    /*哈希函数*/
    int Hash(int key)
    {
        return key % m;     /*除留取余法*/
    }
    12345
    

    插入操作

    /*将关键字插入散列表*/
    void InsertHash(HashTable *H,int key)
    {
         int addr = Hash(Key);             /*求哈希地址*/
         while(H->elem[addr] != NULLKEY)         /*如果不为空则冲突*/
             addr = (addr + 1) % m;           /*线性探测*/
         H->elem[addr] = key;            /*直到有空位后插入关键字*/        
    }   
    12345678
    

    查找操作

    /*查找*/
    Status SearchHash(HashTable H,int key,int *addr)
    {
        *addr = Hash(key);        /*求哈希地址*/
        while(H.elem[*addr] != key)        /*若不为空,则冲突*/
        {
            *addr = (*addr + 1) % m;         /*线性探测*/
            if(H.elem[*addr) == NULLKEY || *addr == Hash(key))
            {/*如果循环回到原点*/
                return UNSUCCESS;        /*则说明关键字不存在*/
            }
        }
        return SUCCESS;
    }   
    1234567891011121314
    

    7、总结

    1、哈希表就是一种以键值对存储数据的结构。
      2、哈希表是一个在空间和时间上做出权衡的经典例子。如果没有内存限制,那么可以
    直接将键作为数组的索引。那么所查找的时间复杂度为O(1);如果没有时间限制,那么我们可以使用无序数组并进行顺序查找,这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

    展开全文
  • 哈希算法实例

    2016-11-23 10:50:44
    原理就像数组下表定位一样,只不过,哈希定位是通过key来定位,这个key是通过哈希函数计算得到的,是一个唯一的值。当然有时会得到重复的key值,那么这是就得解决冲突,典型算法是:用线性补偿探测处理冲突,并处理...
    本程序可以将test.txt文件中的记录按key值存储,然后可以快速查找。原理就像数组下表定位一样,只不过,哈希定位是通过key来定位,这个key是通过哈希函数计算得到的,是一个唯一的值。当然有时会得到重复的key值,那么这是就得解决冲突,典型算法是:用线性补偿探测处理冲突,并处理表溢出。如下面的语句。
            k = 0;
           do {
               l = (l+17) % m;
           } while(ht[l]!="" && ++k<=ht.size());
           if (ht[l] == "")
                ht[l]= name;
           else
           if (k>ht.size()) {
              cout << "哈希表溢出!" << endl;
              overflowBucket.push_back(name);
           }
    完整源码如下:
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    #ifdef WIN32
    #define TEST_FILE   "d:\\work\\proc\\stl\\stl01\\test.txt"
    #else
    #define TEST_FILE   "/tmp/test.txt"
    #endif

    class hashvector
    {
    private:
     vectorht;
     vectoroverflowbucket;
     size_t n;
     size_t m;
    public:
        hashvector(vectornamelist,int mo);
        // 返回表长
        size_t size() const { return m; }
        // 返回表大小
        size_t  table_size()  const { return n; }
        // 返回装填因子
        float load_factor() const { return float(table_size())/size(); }
        // 哈希表插入操作
        void insert(vector& ht,
                      vector& overflowBucket, string name);
        // 哈希表查找操作
        void search(string name);
        // 输出表
        void print_table();
    private:
     size_t mid(size_t s);
     size_t hstr(const string& name);
    };
    hashvector::hashvector(vectornamelist,int m0):m(m0)
    {
     n=namelist.size();
     ht.resize(m);
     for(size_t i=0;i<n;i++)
     {
      insert(ht,overflowbucket,namelist[i]);
     }
    }
    // 首先将参数s平方,然后取其各位数字并保存到数组a,最后返回第4、5位数
    size_t hashvector::mid(size_t s)
    {
       int i=0, a[10];
       size_t d = 1, s0;
       s0 = s*s;
       while(s0>d) d *= 10;
       d /= 10;
       while(d != 0) {
          a[i++] = s0/d;
          s0 = s0%d;
          d = d/10;
       }
       return (a[3]*10+a[4]);
    }
    size_t hashvector::hstr(const string& name)
    {
        // 累加name的ASCII码
        size_t sum = 0, j = 0;
        while(j<name.size()) {
           sum += name[j];  j++;
        }
        return sum;
    }
    void hashvector::insert(vector& ht,
                            vector& overflowBucket, string name)
    {
        size_t  k, s, l;
        // 用除留余数法构造哈希函数
        s = hstr(name);        // 见7.4.2字符串哈希函数
        l = mid(s) % m;         // 除留余数法计算模块
        if (ht[l]=="")
           ht[l] = name;
        else {
           // 用线性补偿探测处理冲突,并处理表溢出
           k = 0;
           do {
               l = (l+17) % m;
           } while(ht[l]!="" && ++k<=ht.size());
           if (ht[l] == "")
                ht[l]= name;
           else
           if (k>ht.size()) {
              cout << "哈希表溢出!" << endl;
              overflowBucket.push_back(name);
           }
        }
    }
    // 在哈希表中查找指定的姓名
    void hashvector::search(string name)
    {
        size_t l;
        bool found = false;
        // 计算哈希函数
        size_t s = hstr(name);
        l = mid(s) % m;
        if (ht[l]==name) {
           cout << name << "已找到!在" << l << "号纪录\n";
           found = true;
        }
        int k = 0;
        while (ht[l]!=name && ht[l]!="" && ++k<=ht.size()) {
            // 线性补偿探测
            l = (l+17) % m;
            if (ht[l]==name && !found) {
              cout << name << "已找到!在" << l << "号纪录\n";
              found = true;
              break;
            }
        }
        if(k>ht.size())
           for (size_t i=0; i<overflowbucket.size(); i++)
               if(overflowbucket[i]==name) {
                  cout << name << "已找到!在溢出桶" << i << "号纪录\n";
                  found = true;
                  break;
               }
        if (!found)
           cout << name << "未找到!\n";
    }
    void hashvector::print_table()
    {
        // 显示建立的哈希表
        size_t j, l;
        cout << "**************************   当前哈希表   *************************\n";
        cout << " 编号                       列信息\n";
      //  j = 0;
        for (l=0; l<m; l++)="" {
           if (ht[l] != "") {
           cout << setw(4) << l << setw(25) << ht[l] << "\t";
             // j++;
           //if ((j+1) % 3==1)
                 cout << endl;
        }
       }
       cout << "\n总人数是: " << table_size() << endl;
       cout << size() << " 个槽已被占用\n" ;
       cout << "装填因子是: " << load_factor() << endl;
    }
    int main(void)
    {
     vectornamelist;
     ifstream ifs(TEST_FILE);
     if (!ifs)
     {
      cerr<<"error open file!"<<endl;
      getchar();
      exit(0);
     }
     int n=35;
     int cnt=0;
     string name;
     //string name2;
     while(ifs>>name  && cnt++<n)
     {
      namelist.push_back(name);
      //namelist.push_back(name2);
        }
        ifs.close();
     hashvector table(namelist,57);
        
     table.print_table();
     name="hhhh";
     table.search(name); 
     getchar();
        return 0;
    }
    展开全文
  • 哈希算法说明示例

    2020-10-30 16:24:37
    定义:哈希算法又叫散列算法,是将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。它的原理其实很简单,就是把一段交易信息转换成一个固定长度的字符串 特点: 1. 信息相同,...

    Hash算法:

    定义:哈希算法又叫散列算法,是将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。它的原理其实很简单,就是把一段交易信息转换成一个固定长度的字符串

    特点:

    1. 信息相同,字符串也相同。

    2. 信息相似不会影响字符串相同。

    3. 可以生成无数的信息,但是字符串的种类是一定的,所以是不可逆的。

    用途:

    1、哈希算法可以检验信息是否是相同的,这样的优势可以节省重复文件传送的时间

    2、哈希算法还可以检验信息的拥有者是否真实

    示例:

    # coding:utf-8 # 使用hashlib模块 import hashlib md5 = hashlib.md5() # 应用MD5算法 data = "hello world" md5.update(data.encode('utf-8'))看 print(md5.hexdigest())

     

    自定义哈希:

    # coding:utf-8 # 自定义哈希函数 def my_hash(x): return (x % 7) ^ 2 print(my_hash(1)) # 输出结果:3 print(my_hash(2)) # 输出结果:0 print(my_hash(3)) # 输出结果:1 print(my_hash(4)) # 输出结果:6

    展开全文
  • 模糊哈希算法又叫基于内容分割的分片分片哈希算法(context triggered piecewise hashing, CTPH),主要用于文件的相似性比较。 2006年,Jesse Kornblum [1] 提出CTPH,并给出一个名为spamsum的算法实例。随后,...

    一、概述

    展开全文
  • 哈希算法原理及其 Java 实现一、目的二、运行环境三、基本原理及步骤(I)各种加密算法的原理:① DES 数据加密标准(Data Encryption Standard):算法介绍算法流程优点缺点破解方式适用场景安全性② 3DES(DES ...
  • Python算法系列-哈希算法

    千次阅读 多人点赞 2020-04-12 23:11:10
    哈希算法一、常见数据查找算法简介二、什么是哈希三、实例:两个数字的和1.问题描述2.双指针办法解决3.哈希算法求解四、总结 哈希算法又称散列函数算法,是一种查找算法。就是把一些复杂的数据通过某种映射关系。...
  • 哈希算法 将任意长度的二进制值串映 射为固定长度的二进制值串,这个映射的规则就是哈希算法, 通过原始数据映射之后得到的二进制值串就是哈希值 需要满足的几点要求 从哈希值不能反向推导出原始数据(所以...
  • 一致性哈希算法

    2020-11-19 17:04:47
    一致性哈希算法在很多领域有应用,例如分布式缓存领域的 MemCache,Redis,负载均衡领域的 Nginx,各类 RPC 框架。在移除或者添加一个服务器时,一致性哈希算法能够尽可能小地改变已存在的服务请求与处理请求服务器...
  • 相信memcache的基本原理大家也都了解过了,memcache虽然是分布式的应用服务,但分布的原则是由client端的api来决定的,api根据存储用的key以及已知的服务器列表,根据key的hash计算将指定的key存储到对应的服务器...
  • 1.历史一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希算法带来的问题,...
  • 一,一致性哈希算法原理 1,一致性哈希算法诞生的背景  技术和业务是相互推动,共同前进的。一致性哈希算法的产生也源于业务的需求。随着业务的增长,一台单机 已经不能满足业务的需要,分布式架构应运而生。...
  • 1、一致性哈希算法的简介  一致性哈希算法是分布式系统中常用的算法,比如有N台缓存服务器,你需要将数据缓存到这N台服务器上。一致性哈希算法可以将数据尽可能平均的存储到N台缓存服务器上,提高系统的负载均衡,...
  • TF-IDF算法原理及Spark源码实例

    千次阅读 2017-02-24 13:33:32
    在Spark中,MLlib有两个算法可以用来计算TF-IDF:HashingTF和TF。 HashingTF从一个文档中计算出给定大小的词频向量。为了将词和向量顺序对应起来,所以使用了哈希。HashingingTF使用每个单词对所需向量的长度S...
  • 一,一致性哈希算法原理 1,一致性哈希算法诞生的背景  技术和业务是相互推动,共同前进的。一致性哈希算法的产生也源于业务的需求。随着业务的增长,一台单机 已经不能满足业务的需要,分布式架构应运而生...
  • 本文会介绍一致性哈希算法原理及其实现,并给出其不同哈希函数实现的性能数据对比,探讨Redis 集群的数据分片实现等,文末会给出实现的具体 github 地址。 Memcached 与客户端分布式缓存 M...
  • 哈希算法 哈希算法,又称为散列函数算法,是一种查找算法。简单来说,就是把一些复杂的数据,通过某种函数映射... 1)什么是哈希:简单介绍什么是哈希哈希的原理 2)两个数的和:快速寻找两个数的和 3)单...
  • 哈希算法(散列算法)简单运用

    千次阅读 2018-10-09 22:49:09
    哈希算法(散列算法) 今天在做LeetCode的时候做到第三题,不包含重复字符的子字符串的最大长度,深刻意识到散列查找的快速性。 核心思想:用空间换时间 哈希算法的核心思想就是用空间复杂度来换取时间复杂度,简单...
  • [转]哈希分布与一致性哈希算法简介

    千次阅读 2012-06-11 02:10:28
    哈希分布与一致性哈希算法简介 作者:liunx 来源:http://www.cnblogs.com/liunx/archive/2010/03/24/1693925.html  前言 在我们的日常web应用开发当中memcached可以算作是当今的标准开发配置了。相信...
  • 是一种基于内容分割的分片哈希算法(context triggered piecewise hashing, CTPH),主要用于文件的相似性比较。 模糊哈希的主要原理: 使用一个弱哈希计算文件局部内容,在特定条件下对文件进行分片(利用弱哈希...
  • 哈希分布与一致性哈希算法简介

    千次阅读 2011-07-19 15:37:33
    前言 在我们的日常web应用开发当中memcached...相信memcache的基本原理大家也都了解过了,memcache虽然是分布式的应用服务,但分布的原则是由client端的api来决定的,api根据存储用的key以及已知的服务器列表,根据key
  • 文章目录前文哈希算法定义和特征哈希算法应用安全加密散列函数唯一标识数据校验 前文   说到哈希算法大家应该都不陌生,但系数它的应用范围,大多数人只能答出少部分,比如用于加密,比如用于散列表,比如MySQL的...
  • 感知哈希本质上是哈希算法中的一类算法,最初被提出来就是用来做相似图片的匹配与计算的,以图搜图的本质也是在做详细图片的计算与匹配,不同的算法会有不同的计算精度和计算速度。 对于我们每个人来说,我们有...
  • 感知哈希算法--python实现

    千次阅读 2016-05-10 21:04:34
    最近在看运动目标跟踪方面的资料,偶然间看到zouxy09大神的一篇《基于感知哈希算法的视觉跟踪》,觉得挺有意思的。于是去查了相关的感知哈希的资料,发现在图片搜索领域里面应用非常广泛,这种技术我觉得有点像模板...
  • 一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希算法带来的问题,使得...
  • 最快的哈希算法

    千次阅读 2017-01-19 17:37:13
     说明:本文分为三部分内容, 第一部分为一道百度面试题Top K算法的详解;第二部分为关于Hash表算法的详细阐述;第三部分为打造一个最快的Hash表算法。  第一部分:Top K 算法详解  问题描述(百度面试题): ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,957
精华内容 13,582
关键字:

哈希算法原理及实例