散列

选择键值,冲突的时候采取不同的策略

散列函数:

简单的散列函数:

1 int hash(const string & key,int tableSize)
2 {
3     int hashVal = 0;
4     for(int i = 0; i < key.length();++i)
5     {
6         hashVal + = key[i];
7     }
8     return hashVal % tableSize;
9 }

比较好的散列函数:

 1 int hash( const string & key,int tableSize )
 2 {
 3     int hashVal = 0;
 4     for(int i = 0; i <key.length();++i)
 5     {
 6         hashVal = 37*hashVal + key[i];
 7     }
 8     hashVal %= tableSize;
 9     if(hashVal < 0)
10         hashVal +=tableSize;
11 
12     return hashVal;
13 }

键的长度和性质 影响选择。

分离链接法

分离链接散列表的类构架

 1 template <typename HashedObj>
 2 class HashTable
 3 {
 4 public:
 5     explicit HashTable( int size = 101);
 6     bool contains (const HashedObj & x) const;
 7     void makeEmpty();
 8     void insert(const HashedObj & x);
 9     void remove(const HashedObj & x);
10 private:
11     vector<list<HashedObj> > theLists;
12     int currentSize;
13     void rehash();
14     int myhash( const HashedObj & x) const;
15 };
16 int hash(const string & key);
17 int hash(int key);

散列表myhash的成员函数:

1 int myhash(const HashedObj & x) const
2 {
3     int hashVal = hash(x);
4     hashVal %= theLists.size();
5     if(hashVal < 0)
6         hashVal += theLists.size();
7     return hashVal;
8 }

使用name成员为键,提供的散列函数实例:

 1 class Employee
 2 {
 3 public:
 4     const string & getName() const
 5     {
 6         return name;
 7     }
 8     bool operator==( const Employee & rhs ) const
 9     {
10         return getName() == rhs.getName();
11     }
12     bool operator!=(const Employee & rhs) const
13     {
14         return !(*this == rhs);
15     }
16 private:
17     string name;
18     double salary;
19     int seniority;
20 };
21 int hash(const Employee & item)
22 {
23     return hash(item.getName());
24 }

实现makeEmpty contains remove:

 1 void makeEmpty()
 2 {
 3     for(int i =0;i<theLists.size();i++)
 4         theLists[i].clear();
 5 }
 6 bool contains(const HashedObj & x) const
 7 {
 8     const list<HashedObj> & whichList = theLists[myhash(x)];
 9     return find(whichList.begin(),whichList.end(),x)!=whichList.end();
10 }
11 bool remove(const HashedObj & x) const
12 {
13     list<HashedObj> & whichList = theLists[myhash(x)];
14     list<HashedObj>::iterator itr = find(whichList.begin(),whichList.end(),x);
15 
16     if(itr == whichList.end())
17         return false;
18     
19     whichList.erase(itr);
20     --currentSize;
21     return true;
22 }

分离散列表的insert实例

 1 bool insert(const HashedObj & x)
 2 {
 3     list<HashedObj> & whichList = theLists[myhash(x)];
 4     if(find(whichList.begin(),whichList.end(),x)!=whichList.end())
 5         return false;
 6     whichList.push_back(x);
 7     if(++currentSize > theLists.size())
 8         rehash();
 9 
10     return true;
11 }

装填因子:散列表中的元素个数 与 散列表大小的 比值

执行一次查找所需的时间:计算散列函数值所需要的常数时间加上遍历表所用的时间

不使用链表的散列表:

当冲突发生时,直接寻找下一单元

<线性探测>

<平方探测>

使用探测策略的散列表的类接口

 1 template <typename HashedObj>
 2 class HashedObj
 3 {
 4 public:
 5     explicit HashTable(int size = 101);
 6     bool contains(const HashedObj & x) const;
 7     void makeEmpty();
 8     bool insert(const HashedObj & x);
 9     bool remove(const HashedObj & x);
10     enum EntryType{ACTIVE,EMPTY,DELETED};
11 private:
12     struct HashEntry
13     {
14         HashedObj element;
15         EntryType info;
16 
17         HashEntry(const HashedObj & e = HashedObj(),EntryType i = EMPTY):element(e),info(i){}
18     };
19     vector<HashEntry> array;
20     int currentSize;
21     bool isActive(int currentPos) const;
22     int findPos(const HashedObj & x) const;
23     void rehash();
24     int myhash(const HashedObj & x) const;
25 };

初始化平方探测散列表

 1 explicit HashTable(int size = 101):array(nextPrime(size))
 2 {
 3     makeEmpty();
 4 }
 5 void makeEmpty()
 6 {
 7     currentSize = 0;
 8     for(int i = 0 ; i < array.size(); i++)
 9         array[i].info = EMPTY;
10 }

使用平方探测进行散列的contains findPos isActive

 1 bool contains(const HashedObj & x) const
 2 {
 3     return isActive(findPos(x));
 4 }
 5 int findPos(const HashedObj & x) const
 6 {
 7     int offset = 1;
 8     int currentPos = myhash(x);
 9 
10     while(array[currentPos].info != EMPTY && array[currentPos].element != x)
11     {
12         currentPos += offset;
13         offset += 2;
14         if(currentPos >= array.size())
15             currentPos -= array.size();
16     }
17     return currentPos;
18 }
19 bool isActive(int currentPos) const
20 {
21     return array[currentPos].info == ACTIVE;
22 }

使用平方探测的insert remove

bool insert( const HashedObj & x)
{
    int currentPos = findPos(x);
    if(isActive( currentPos ))
        return false;
    array[currentPos] = HashEntry(x,ACTIVE);
    if(++currnetSize>array.size()/2)
        rehash();
}
bool remove(const HashedObj & x)
{
    int currentPos = findPos(x);
    if(!isActive(currentPos))
        return false;
    array[currentPos].info = DELETED;
    return true;
}

<双散列>

对分离散列表的再散列

 1 void rehash()
 2 {
 3     vector<HashEntry> oldArray = array;
 4     array.size(nextPrime(2*oldArray.size()));
 5     for(int j = 0; j < array.size(); j++)
 6     {
 7         array[j].info = EMPTY;
 8     }
 9     currentSize = 0;
10     for(int i = 0; i < array.size(); i++)
11     {
12         if(oldArray[i].info == ACTIVE)
13             insert(oldArray[i].element);
14     }
15 }

对探测散列表的再散列

 1 void rehash()
 2 {
 3     vector<list<HashedObj> > oldLists = theLists;
 4     theLists.resize( nextPrime( 2*theLists.size() ) );
 5     for(int j = 0; j < theLists.size(); j++)
 6     {
 7         theLists[j].clear();
 8     }
 9     currentSize = 0;
10     for(int i = 0; i < oldLists.size(); i++)
11     {
12         list<HashedObj>::iterator itr = oldLists[i].begin();
13         while( itr != oldLists[i].end( ) )
14             insert(*itr++);
15     }
16 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏c#开发者

BizTalk Orchestration execute Flat file disassembler ReceivePipeline

需求是这样,在一个inbound XML中有个一点节点使用平文件的方式存放,还要解析比如固定长度或根据特殊字符截取字段 也就是需要在流程里面先把输入的XML的节...

375130
来自专栏猿份到

LeakCanary源码浅析

在Android开发中最让人们头疼的就是内存泄漏了,今天来介绍一个查看内存是否泄漏的工具LeakCanary,并通过研究源码明白它是如何分析和查找存在泄漏信息的...

35850
来自专栏IT笔记

聊一聊生产环境中如何动态监听配置文件变化并重载

上一篇,我们谈到Java中的几种读取properties配置文件的方式,但是在生产环境中,最忌讳的就是重启应用了。比如某个系统的路径常量或者接口变更,需要线上及...

474110
来自专栏大内老A

ASP.NET Core中的依赖注入(5): ServiceProvider实现揭秘 【总体设计 】

本系列前面的文章我们主要以编程的角度对ASP.NET Core的依赖注入系统进行了详细的介绍,如果读者朋友们对这些内容具有深刻的理解,我相信你们已经可以正确是使...

22060
来自专栏陈树义

简单笔记

1、类的表面类型和实际类型 实例对象有两个类型:表面类型(Apparent Type)和实际类型(ActualType),表面类型是声明时的类型,实际类型是对象...

26750
来自专栏刘望舒

手动实现Android热修复

周一发布了新版本,当天晚上用户就为app未测试到的bug发飙了,恩,很快就找到了问题所在,一个容易疏忽的空指针。虽然只是一个小小的bug但是不修复是很影响用户体...

21850
来自专栏编码前线

Redis命令:scan实现模糊查询

从Redis v2.8开始,SCAN命令已经可用,它允许使用游标从keyspace中检索键。 对比KEYS命令,虽然SCAN无法一次性返回所有匹配结果,但是却规...

51730
来自专栏技术博客

Asp.Net Web API 2第十六课——Parameter Binding in ASP.NET Web API(参数绑定)

阅读本文之前,您也可以到Asp.Net Web API 2 系列导航进行查看 http://www.cnblogs.com/aehyok/p/3446289.h...

10130
来自专栏java一日一条

Java 容器相关知识全面总结

Java实用类库提供了一套相当完整的容器来帮助我们解决很多具体问题。因为我本身是一名Android开发者,包括我在内很多安卓开发,最拿手的就是ListView(...

13210
来自专栏Danny的专栏

静态代理与动态代理

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

9430

扫码关注云+社区

领取腾讯云代金券