`
java-大神
  • 浏览: 34935 次
  • 性别: Icon_minigender_1
  • 来自: 大山东
社区版块
存档分类
最新评论

哈希表 我的初中

阅读更多

 

   

    前些天胡哥给讲哈希表,悔恨自己没提前看下书,导致后来小伙伴们登台讨论的热火朝天时自己只能充当观众,那酸爽,唉...

    当天回家恶补数据结构,发现哈希表其实还是挺容易理解的,就是在实现上面会感觉无从下手,因为自己还没有真正处理过大数据(虽然最近在研究大数据~~),只好自己敲个小程序cos下。

    当天在胡哥课上除了哈希表基本思想外,印象最深的就是哈希表的冲突问题,当时听的时候感觉挺高大上,不理解冲突是个什么东东,为什么会发生?后来想了下,我去,不就是初中学过的抽屉原理吗,忘记了的小伙伴请回校复读,哈哈。

额,顺便插一句,推荐大家看一下下面这个视频http://v.163.com/movie/2010/12/R/E/M6UTT5U0I_M6V2TG4RE.html

麻省理工关于哈希算法的公开课,那光头讲的很细致,通俗易懂吧,楼主耐着性子看完后觉得这4664秒还是挺值得的,想感受下的同学不妨看下。

<!--EndFragment-->

    好了,言归正传,下面主要说一下自己堆哈希表理解最深的构造方法与解决冲突法方法。

<!--EndFragment-->

    哈希表的基本构造方法
    构造哈希表的方法是:设要存储的数据元素个数为n,设置一个长度为m(m≥n)的连续内存单元(即数组),分别以每个数据元素的关键字Ki(0≤i≤n-1)为自变量,以哈希函数h(Ki)值为该数据元素在数组中的下标值存储该数据元素。
    把构造哈希表时Ki≠Kj(i≠j),但h(Ki)=h(Kj)的现象称作哈希冲突。

    哈希表的构造方法百科上介绍了许多,比如:数字分析,平方取中,伪随机,折叠啊,取余啊。

    这里说一下楼主理解最深的折叠法与平方取中法。

    折叠法是按哈希表地址位数将关键字分成位数相等的几部分(最后一部分可以较短),然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。折叠法是从一端向另一端沿分割界来回折叠(奇数段为正序,偶数段为倒序),然后将各段相加。

    例如:key=123 603 247 112 020 65,哈希表长度为1000,则应把关键字分成3位一段,在此舍去最低的两位65,分别进行移位叠加和折叠叠加,求得哈希地址为907。

       1 2 3

       3 0 6

       2 4 7

       2 1 1

 +)0 2 0

——————  

       9 0 7

    平方取中

    如果是以字符串形式出现该怎么办呢?

    例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11E的内部编码为05Y的内部编码为25A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501,同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后,取出第7到第9位作为该关键字哈希地址。

   

关键字

内部编码

内部编码的平方值

H(k)关键字的哈希地址

KEYA

11050201

122157778355001

778

KYAB

11250102

126564795010404

795

AKEY

01110525

001233265775625

265

BKEY

02110525

004454315775625

315

<!--EndFragment-->

    冲突问题

    通过构造性能良好的哈希函数,可以减少冲突,但一般不可能完全避免,因此解决冲突是哈希表的另一个关键问题。常用的解决办法有;开放地址法,再哈希法,链地址法以及建立公共溢出区。

    开放地址法的基本思想是:当关键字key的哈希地址p=Hkey)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,直到找出一个不冲突的哈希地址pi 将相应元素存入其中。这种方法有一个通用的再散列函数形式:

     Hi=Hkey+di% m   i=12,…,n

    其中Hkey)为哈希函数,为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。

    这里说一下线性探测再散列:(后文代码中会体现)

    dii=123,…,m-1

    特点:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

     再哈希法(Rehash)是同时构造多个不同的哈希函数:

     Hi=RH1key)  i=12,…,k

     当哈希地址Hi=RH1key发生冲突时,再计算Hi=RH2key)……,直到冲突不再产生。比较费时。

 

     关于布隆过滤器,像了解的同学可以到下面网址学习,楼主也只是简单了解下,就不再啰嗦

http://www.cnblogs.com/dolphin0520/archive/2012/11/10/2755089.html

    下面是关于哈希表的简单代码

#include<iostream>  
using namespace std;  
  
typedef int KeyType; //设关键字域为整形,需要修改类型时,只需修改这里就可以  
const int NULLKEY=0; //NULLKEY表示该位置无值  
int c=0; //用来统计冲突次数  
  
struct Elemtype //数据元素类型  
{  
    KeyType key;  
    int ord;   
};  
  
int hashsize[]={11,19,29,37,47}; //hash表容量递增表  
int Hash_length=0;//hash表表长  
  
class HashTable  
{  
private:  
    Elemtype *elem; //数据元素数组,动态申请  
    int count;// 当前数据元素个数  
    int size; //决定hash表的容量为第几个,hashsize[size]为当前hash容量  
public:  
  
    int Init_HashTable() //初始化哈希表  
    {  
        int i;  
        count=0;  
        size=0; //初始化容量为hashsize[0]=11  
        Hash_length=hashsize[0];  
        elem=new Elemtype[Hash_length];  
        if(!elem)  
        {  
            cout<<"内存申请失败"<<endl;  
            exit(0);  
        }  
        for(i=0;i<Hash_length;i++)  
            elem[i].key=NULLKEY;  
        return 1;  
    }  
  
    void Destroy_HashTable()  
    {  
        delete[]elem;  
        elem=NULL;  
        count=0;  
        size=0;  
    }  
  
    unsigned Hash(KeyType k) //hash函数的一种(取模法)  
    {  
        return k%Hash_length;  
    }  
  
    void Collision(int &p,int d) //解决冲突  
    {  
        p=(p+d)%Hash_length; //采用开放地址法里的线性探测  
    }  
  
    bool Search_Hash(KeyType k,int &p) //查找  
    {  
        //在开放地址hash表中查找关键字等于k的元素  
        //若找到用p表示待查数据,查找不成功时,p指向的是可插入地址  
        c=0;  
        p=Hash(k); //求hash地址  
        while(elem[p].key!=NULLKEY && elem[p].key!=k)  
        {  
            c++;  
            if(c<Hash_length)  
                Collision(p,c);  
            else  
                return 0; //表示查找不成功  
        }  
        if(elem[p].key==k)  
            return 1;  
        else  
            return 0;  
  
    }  
  
    int Insert_Hash(Elemtype e) //插入  
    {  
        //在查找不成功的情况下将k插入到hash表中  
        int p;  
        if(Search_Hash(e.key,p))  
            return -1; //表示该元素已在hash表中  
        else if(c<hashsize[size]/2) //冲突次数未达到上限  
        {  
            //插入e  
            elem[p]=e;  
            count++;  
            return 1;  
        }  
        else  
            ReCreate_HashTable(); // 重建hash表  
        return 0; //插入失败  
    }  
  
    void ReCreate_HashTable() //重建hash表  
    {  
        int i,count2=count;  
        Elemtype *p,*elem2=new Elemtype[count];  
        p=elem2;  
        cout<<"____重建hash表_____"<<endl;  
        for(i=0;i<Hash_length;i++) //将原有元素暂存到elem2中  
            if(elem[i].key!=NULLKEY)  
                *p++=*(elem+i);  
        count=0;  
        size++; //hash容量增大  
        Hash_length=hashsize[size];  
        p=new Elemtype[Hash_length];  
        if(!p)  
        {  
            cout<<"空间申请失败"<<endl;  
            exit(0);  
        }  
        elem=p;  
        for(i=0;i<Hash_length;i++)  
            elem[i].key=NULLKEY;  
        for(p=elem2;p<elem2+count2;p++) //将原有元素放回新表  
            Insert_Hash(*p);  
    }  
  
    void Traverse_HashTable()  
    {  
        cout<<"哈希地址0->"<<Hash_length-1<<endl;  
        for(int i=0;i<Hash_length;i++)  
            if(elem[i].key!=NULLKEY)  
                cout<<"元素的关键字值和它的标志分别是:"<<elem[i].key<<"  "<<elem[i].ord<<endl;  
  
    }  
  
    void Get_Data(int p)  
    {  
        cout<<"元素的关键字值和它的标志分别是:"<<elem[p].key<<"  "<<elem[p].ord<<endl;  
    }  
      
}; 

int main()  
{  
    Elemtype r[12]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{5,9},{6,10},{7,11},{8,12}};  
    HashTable H;  
    int i,p,j;  
    KeyType k;  
    H.Init_HashTable();  
    for(i=0;i<11;i++) //插入前11个记录  
    {  
        j=H.Insert_Hash(r[i]);  
        if(j==-1)  
            cout<<"表中已有关键字为"<<r[i].key<<"  "<<r[i].ord<<"的记录"<<endl;  
    }  
  
    cout<<"按哈希地址顺序遍历哈希表"<<endl;  
    H.Traverse_HashTable();  
    cout<<endl;  
  
    cout<<"输入要查找的记录的关键字:";  
    cin>>k;  
    j=H.Search_Hash(k,p);  
    if(j==1)  
        H.Get_Data(p);  
    else  
        cout<<"无此记录"<<endl;  
  
    j=H.Insert_Hash(r[11]); //插入最后一个元素  
    if(j==0)  
    {  
        cout<<"插入失败"<<endl;  
        cout<<"需要重建哈希表才可以插入"<<endl;  
        cout<<"____重建哈希表____"<<endl;  
        H.Insert_Hash(r[i]); //重建后重新插入  
    }  
  
    cout<<"遍历重建后的哈希表"<<endl;  
    H.Traverse_HashTable();  
    cout<<endl;  
  
    cout<<"输入要查找的记录的关键字:";  
    cin>>k;  
    j=H.Search_Hash(k,p);  
    if(j==1)  
        H.Get_Data(p);  
    else  
        cout<<"该记录不存在"<<endl;  
  
    cout<<"____销毁哈希表____"<<endl;  
    H.Destroy_HashTable();  
  
    return 0;  
}  

 

  

<!--EndFragment--><!--EndFragment--><!--EndFragment--><!--EndFragment--><!--EndFragment-->
分享到:
评论

相关推荐

    台州市2023年青少年信息学竞赛复赛试题(初中组)

    **解题思路**:可以通过遍历每个学生,利用哈希表记录每个斜率下的学生数量,从而判断是否有k个学生能够站成一条直线。 #### 找数对 **题目描述**:对于给定的n个正整数,求出满足条件(aj^2 )的数对(a_j, a_k)的...

    算法 课件和源码(初中高)

    2. 搜索算法:如线性搜索、二分查找、哈希表查找等,帮助在数据集中定位特定元素。 3. 图算法:如Dijkstra算法(最短路径)、Floyd-Warshall算法(所有对最短路径)、Prim算法和Kruskal算法(最小生成树)等,应用...

    Java高级知识

    - `LinkedHashSet`: 哈希表+链表,保持插入顺序 - `TreeSet`: 红黑树实现,自然排序或自定义排序 - **Map** - `HashMap`: 基于哈希表,不保证键值对顺序 - `LinkedHashMap`: 保持插入顺序 - `TreeMap`: 自然排序或...

    CSP-J 第3套初赛模拟试题模拟题附答案

    - **题目描述**:给定四个数值(2, 6, 10, 17),要求设计一个哈希函数,使得这些数值存入哈希表时不会发生冲突。 - **解析**: - 本题考查哈希函数的设计与冲突处理。 - 一种可行的哈希函数设计为\(h(x) = x \mod b...

    编程算法题(适合初学人看看)

    8. **数据结构**:如数组、链表、栈、队列、树、哈希表等,它们是算法的载体,理解和运用合适的数据结构能有效提高算法效率。 Java作为面向对象的语言,其丰富的类库和强大的功能使得实现各种算法变得简单。在初学...

    国际程序设计大赛的作品欣赏

    例如,平衡二叉搜索树(AVL、红黑树)常用于快速查找,哈希表则适合高效查找和去重。 此外,优化技巧也是关键。参赛者需要考虑时间复杂度和空间复杂度,通过代码优化减少运行时间和内存消耗。常用技巧包括:剪枝...

    数据结构与算法 -电子教案

    它包括数组、链表、栈、队列、树、图、哈希表等多种类型。例如,数组提供随机访问,但插入和删除操作效率低;链表则允许动态改变大小,但访问速度慢。栈遵循“后进先出”(LIFO)原则,常用于函数调用和表达式求值;...

    ASP.NET实例开发源码——初中校园成绩查询系统.zip

    这个实例开发源码——初中校园成绩查询系统,是利用ASP.NET技术实现的一个具体应用,旨在帮助初中的教务人员、教师和学生进行成绩的查询与管理。 在ASP.NET中,开发人员通常使用C#或VB.NET作为后端编程语言,结合...

    NOIP2017提高组初复赛试题与题解报告

    而复赛则更加强调复杂算法的设计和应用,例如动态规划、贪心策略、图论算法(深度优先搜索、广度优先搜索、最短路径算法如Dijkstra或Floyd)以及数据结构(栈、队列、树、图、哈希表等)。 报告中对于每一道题目,...

    全国信息学竞赛noip07年普及组复赛试题与测试数据

    3. **数据结构**:链表、栈、队列、数组、哈希表等,这些是解决复杂问题的关键工具,选手需要理解它们的工作原理以及如何在实际问题中应用。 4. **逻辑思维**:解决信息学竞赛中的问题往往需要严谨的逻辑推理,比如...

    考试类精品--历年CSP考试 题解.zip

    2. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL、红黑树)、哈希表、堆(最大堆、最小堆)、图等。 3. **编程语言基础**:熟悉至少一种编程语言,如C++、Python或Java,理解变量、控制流(条件...

    CCF相关认证比赛介绍-2019-11-21.rar

    2. **数据结构**:数组、链表、栈、队列、哈希表、树(二叉树、平衡树如AVL和红黑树)、图等。 3. **逻辑思维**:通过分析问题,设计合理的算法流程,解决实际问题。 4. **编程语言基础**:通常使用C++或Python...

    2018蓝桥杯VIP题

    2. **数据结构**:链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图、堆、哈希表等,理解它们的特性并能灵活运用。 3. **动态规划**:解决复杂问题的有效方法,要求选手能够构建状态转移方程并设计记忆化...

    信息学全国联赛普及组2015-2018年c++初赛真题和答案

    - 链表、数组、栈、队列、哈希表、树等数据结构在竞赛中频繁出现。理解和熟练运用这些数据结构是解决复杂问题的关键。 4. **逻辑思维与问题解决能力**: - 能够读懂题目,分析问题,设计出有效的解决方案,并用...

    CCFCSP认证试题 21年和22年真题分析.zip

    2. 数据结构运用:链表、栈、队列、树、图、哈希表等,理解其特性并灵活运用。 3. 动态规划思路:理解状态转移方程,避免重复计算,构建记忆化搜索或自底向上的解决方案。 五、模拟训练 1. 定期练习:通过模拟题和...

    ACM NOI 信息学竞赛 国家集训队2008论文集

    2. **数据结构**:包括数组、链表、栈、队列、树(二叉树、平衡树如AVL、红黑树等)、图、哈希表等,以及如何在实际问题中灵活应用它们。 3. **问题解构与建模**:如何将复杂问题转化为计算机可以处理的形式,如...

    蓝桥杯题目和测试数据第一部分

    - **数据结构**:链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、哈希表等都是常见的考察点。 - **数学与逻辑**:数论问题(质数、模运算)、组合数学、逻辑推理等也可能出现在题目中。 在准备蓝桥杯的过程...

    NOIP10-18普及组试题及官方数据

    二分查找和哈希表则常用于高效的数据查找。 3. **逻辑推理**:一些试题会设计成逻辑谜题,要求参赛者运用逻辑推理能力来解决问题,这在训练学生的逻辑思维和分析能力方面有很大帮助。 4. **测试数据**:官方提供的...

    noip2011普及组试题

    2. **数据结构**:数组、链表、栈、队列、哈希表、树(二叉树、平衡树、堆)、图等。 3. **逻辑思维**:如何分析问题、分解任务、设计算法。 4. **编程语言**:C++或Python是最常见的竞赛编程语言,需要熟练掌握...

    初中语文文摘情感爱如薄冰挽断罗衣留不住

    "所谓的前世今生,你终究是用了逃逸作为注脚",这里提到了时间和变化的主题,这在区块链技术中有所体现,每个区块记录了时间戳和前一个区块的哈希值,形成不可篡改的时间线。 最后,"情缘散尽,痴心却不改",情感的...

Global site tag (gtag.js) - Google Analytics