浅谈哈希思想的应用

标签: 哈希 思想 应用 | 发表时间:2011-09-10 12:07 | 作者:远野嘉一 叽歪陈
出处:http://www.cppblog.com/
前言
      散列表(HashTable)又称为哈希表,是一种快速的数据查找结构,它通常是为一个(组)要记录的数据设计一个哈希函数H(x),依据这个函数进行给数据定位,如果是闭散列,那就是直接存到数组的H(x)下标处,如果是开散列,就是存到指针数组H(x)下标的链表处。在OI中某些Pascaler为了避开链表而采用的闭散列鄙人认为相当糟糕,至于原因会在后面解释。所以本文只谈开散列。

哈希表的组织方式:
      我们首先要确定一个哈希函数H(x),x是要记录的对象,我们以H(x)来确定对象的记录的链的位置。
      还需要一个指针数组来存放每个链的头指针。由于要使用链表,所以还要有一个class/struct作为链表的基本单位。
哈希表的一般实现:
首先是链表的基本元素:
template<class T>
struct t_node
{
    
public:
        T key;
        
//other info
        t_node* next;
}
;

然后是HashTable类的骨架(我在这里把它封装成类了):

template<class T>
class hashtable
{
    
public:
        hashtable();
        
int hash(const T &sr);
        
void insert();
        t_node 
*find(const T &sr);
        
//add more functions
    private:
        t_node 
*ht[t_size];//you should define t_size as sth before
        
//add more things
}
;

接下来是构造函数:

hashtable<T>::hahstable()
{
    memset(ht,
0,sizeof(ht));
}

先略去哈希函数,介绍插入函数:

void hashtable<T>::insert(const T &sr)
{
    
int loc = hash(sr);
    
if (ht[loc] == 0)
    
{
        
//此处为空,插入一个新链表
        ht[loc] = new t_node();
        ht[loc]
-> key = T;
    }

    
else
    
{
        t_node 
*now = ht[loc];
        
while (true)
        
{
            
if (now->key == sr)
            
{
                
//元素已经存在。 
                return;
            }

            
else if (now->next == 0)
            
{
                
//链里面没有该元素,就地插入
                now->next = new t_node();
                now
->next->key = T; 
                
return;
            }

            
else now = now->next;
        }

    }

}

然后是查找:

t_node *hashtable<T>::find(const T &st)
{
    
int loc = hash(sr);
    
if (ht[loc] == 0)
    
{
        
//此处为空,木有~ 返回空指针 
        return 0;
    }

    
else
    
{
        t_node 
*now = ht[loc];
        
while (true)
        
{
            
if (now->key == sr)
            
{
                
//找到了 
                return now;
            }

            
else if (now->next == 0)
            
{
                
//遍历完了整个链还是木有。。 
                return 0;
            }

            
else now = now->next;//看这个链的下一个元素 
        }

    }

}

当然可以根据具体情况做各种改动,如果要极限追求效率可以在t_node里面把key改为指针,然后使用自己编写的内存分配函数代替new。


最简单的哈希函数:
其实最简单的哈希表1就是H(x)=x,意思是若记录对象是整数,就直接采用这个整数为下标(char类型也可视为整数),这个就是数组,但它也可以看作哈希表。
最简单的哈希表2就是H(x)=1,意思是不管是什么元素都放到同一个下标,这个就是链表,也可视为一种哈希表。

大整数的哈希函数:
当记录对象是大整数的时候,若再用H(x)=x,数组的范围将会承受不起,所以这时候要考虑哈希函数的设计问题,又有很多种设计方法,最广泛的一种就是H(x)=x%k,k通常是一个质数。

一般的哈希函数:
我们也许会记录一些class或者struct之类的东西,这时候我们可以选取里面的某些关键变量进行一种运算来确定下标。

冲突的处理:
再好的哈希函数也很难避免冲突,所谓冲突就是说H(a)=H(b)的情况,而开散列的处理方法是在数组后面挂的是链表,这样冲突的元素可以直接挂在链表的末端,而闭散列没有链表,一般是重复Hn(x)或者往H(x)+a(a=1,2,3..)寻找,这会使哈希表变得一塌糊涂,而且冲突还可能引发别的冲突,而且也不便于估计哈希数组的范围,所以鄙人不提倡使用闭散列的组织方式。
顺便说一句:好的哈希函数是尽量减少和平衡冲突,尽量使得每个链的长度分布得平均,好的哈希函数的设计要靠长久的经验积累,绝非一日之功。

哈希表的本质思想:
散列表本质思想就是把数组与链表的优势结合起来,数组的访问复杂度是O(1),链表的插入复杂度是O(1),然而数组的插入复杂度和链表的访问复杂度都比较高,所以就产生了散列表。我们可以把这个思想运用到许多地方,这本是我想说的重点,但鄙人才疏学浅,不知如何表达,日后整理一下代码说明吧。



远野嘉一 2011-09-10 12:07 发表评论

相关 [哈希 思想 应用] 推荐:

浅谈哈希思想的应用

- 叽歪陈 - C++博客-首页原创精华区
前言       散列表(HashTable)又称为哈希表,是一种快速的数据查找结构,它通常是为一个(组)要记录的数据设计一个哈希函数H(x),依据这个函数进行给数据定位,如果是闭散列,那就是直接存到数组的H(x)下标处,如果是开散列,就是存到指针数组H(x)下标的链表处. 在OI中某些Pascaler为了避开链表而采用的闭散列鄙人认为相当糟糕,至于原因会在后面解释.

一致性哈希算法及其在分布式系统中的应用

- BeerBubble - 博客园-EricZhang&#39;s Technology Blog
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用. 首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接下来会对这个算法进行相对详细的描述,并讨论一些如虚拟节点等与此算法应用相关的话题.

一致性哈希算法 - Consistent Hashing

- - CSDN博客云计算推荐文章
一、简单介绍一致性哈希算法.         分布式存储中,常常涉及到负载均衡问题,由于有多个数据存储服务器. 因此当一个对象被保存时候,它究竟应该存放到哪个数据存储服务器上面呢.         又例如:现在假设有一个网站,最近发现随着流量增加,服务器压力越来越大,之前直接读写数据库的方式已经不能满足用户的访问,于是想引入 Memcached 作为缓存机制.

一致性哈希算法(consistent hashing)

- - 互联网 - ITeye博客
consistent hashing由来. 在麻省理工学院用作分布式缓存,现在已经扩大到其他领域. 它被设计来解决hash的什么问题. 假设有m个对象需要被映射到n个node上,简单hash就求余映射hash(object)%n->node,就大致均匀的分布到n个node上了. 可是问题在于如果n发生变化(多了或者少了),就必须重新计算保存对象存放到node,这代价未免有点大.

局部敏感哈希介绍

- - 鸟窝
传统的Hash当源数据有些许的变化的时候生成的哈希值差异也非常的大, 比如:. s1 := []byte("你好世界"). s2 := []byte("你好,世界"). s1的哈希值是 65396ee4aad0b4f17aacd1c6112ee364、s2的哈希值是 27444ee2d245c3e8e11ed8b9b035c43b,源数据仅仅是一个逗号的区别,但是哈希值完全不一样.

“分布式哈希”和“一致性哈希”的概念与算法实现

- Wolf - 搜索研发部官方博客
  分布式哈希和一致性哈希是分布式存储和p2p网络中说的比较多的两个概念了. 介绍的论文很多,这里做一个入门性质的介绍.   两个key point:每个节点只维护一部分路由;每个节点只存储一部分数据. 从而实现整个网络中的寻址和存储. DHT只是一个概念,提出了这样一种网络模型. 并且说明它是对分布式存储很有好处的.

法国考虑宣布哈希密码非法

- 推子 - Solidot
根据法国议会正在讨论中的一项数据保留法律,如果密码不是以明文而是以哈希密码形式储存,将被宣布为非法. 根据这项新法律,电子商务网站、视频和音乐服务,以及Web电子邮件供应商必须保留用户数据一年;用户数据必须包括用户全名、邮编地址、电话号码和密码;如果官方要求网站必须递交用户数据,警方、海关、税务和社会保险机构有权访问数据.

哈希表的使用场景--大数据中的前k大

- - CSDN博客推荐文章
下面就以一个网上很常见的面试题作为分析对象:.     一个10G的关键词的log,找出词频最高的前K个词,设可用内存为2G左右.     本题的难点主要有两处,一是如何在有限内存下对大文件进行词频统计;二是如何在有限内存的下找出词频的前K大个词.     词频统计,我们很自然的会想到使用hash.

相似图片搜索的三种哈希算法

- - CSDN博客推荐文章
想必大家都用google或baidu的识图功能,上面就是我搜索冠希哥一幅图片的结果,达到图片比较目的且利用信息指纹比较有三种算法,这些算法都很易懂,下面分别介绍一下:. 一、平均哈希算法(aHash). 此算法是基于比较灰度图每个像素与平均值来实现的,最适用于缩略图,放大图搜索. 1.缩放图片:为了保留结构去掉细节,去除大小、横纵比的差异,把图片统一缩放到8*8,共64个像素的图片.

一致性哈希算法与Java实现

- - Java - 编程语言 - ITeye博客
一致性哈希算法是分布式系统中常用的算法. 比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了,如果是持久化存储则要做数据迁移,如果是分布式缓存,则其他缓存就失效了.