C++实现哈希映射(与map二叉树映射，线性映射比较)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++实现哈希映射(与map二叉树映射，线性映射比较)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2477字，纯文字阅读大概需要4分钟。

内容图文

practice1.h(包含线性映射)

#ifndef PRACTICE1_H_INCLUDED
#define PRACTICE1_H_INCLUDED

#include<vector>

template<class Key,class Value>

class LinerMap //线性映射
{
 public:
     LinerMap(int size=101):arr(size)
     {

         currentSize=0;
     }
     void Put(const Key&k,const Value & v)
     {

         arr[currentSize]=DataEntry(k,v);
         currentSize+=1;
     }
     Value Get(const Key & k)
     {

         //线性查找
         for(size_t i=0;i<currentSize;i++)
         {

             if(arr[i].key==k)
                return arr[i].value;
             else
                return 2333;
         }
     }
private:
    struct DataEntry{
     Key key;
     Value value;
     DataEntry(const Key &k=Key(),
               const Value & v=Value()):
                   key(k),value(v) {}
    };
    std::vector<DataEntry> arr;
    int currentSize;
};

#endif // PRACTICE1_H_INCLUDED

hashmap.h文件

#ifndef HASHMAP_H_INCLUDED
#define HASHMAP_H_INCLUDED

#include<vector>

template<class Key,class Value>

class HashMap //哈希映射
{
 public:
     HashMap(int size=101):arr(size)
     {

         currentSize=0;
     }
     void Put(const Key&k,const Value & v)
     {
         int pos=myhash(k);
         arr[pos]=DataEntry(k,v);
         ++currentSize;
     }
     Value Get(const Key & k)
     {
            int pos=myhash(k);
            if(arr[pos].key==k)
                return arr[pos].value;
            else
                return Value();

     }
     unsigned hash(const Key & k) const
     {
         unsigned int hashVal=0;
         const char *keyp=reinterpret_cast<const char *>(&k);//转换成字符
         for (size_t i=0;i<sizeof(Key); i++)
             hashVal=37*hashVal+keyp[i];
         return hashVal;

     }//哈希函数不能太过于复杂 不然影响执行速度

     int myhash(const Key & k)const
     {

         unsigned hashVal=hash(k);
         hashVal %=arr.size();
         return hashVal;
     }
private:
    struct DataEntry{
     Key key;
     Value value;
     DataEntry(const Key &k=Key(),
               const Value & v=Value()):
                   key(k),value(v) {}
    };
    std::vector<DataEntry> arr;
    int currentSize;
};

#endif // PRACTICE1_H_INCLUDED

practice.cpp文件

#include<iostream>
#include<map>//映射，二叉树映射(字典），不是哈希映射
#include "practice1.h"
#include<string>


#include<hash_map>//不是c++的国际标准里
#include "hashmap.h"
using namespace std;

int main()
{
    //二叉搜索树
    map<string,int> m;//字典
    m["bill"]=98;
    //保存了许多

    //cout<<m["bill"]<<endl;
    //速度是logn
    //哈希是O（1）

    //数组的优点  查询特别快

    //线性查找
//    LinerMap<string,int> lm;
//
//    lm.Put("bill",80);
//
//    lm.Put("jack",100);
//
//    cout<<lm.Get("bill")<<endl;



   //哈希映射

   HashMap<string,int>myHMap;
//   cout<<myHMap.hash("bill")<<endl;//得到bill的哈希值
//   cout<<myHMap.myhash("bill")<<endl;
   //哈希值特别大可以再对数组的容量进行一次取余
//   myHMap.Put("bin",999);
//   cout<<myHMap.myhash("bin")<<endl;
//   myHMap.Put("jack",100);
//   cout<<myHMap.myhash("jack")<<endl;
//
//   cout<<myHMap.Get("jack")<<endl;




    //c++制作好的哈希映射
    hash_map<string,int> hm;
    hm["libin"]=15;
    cout<<hm["libin"]<<endl;

    return 0;
}

 

内容总结

以上是互联网集市为您收集整理的C++实现哈希映射(与map二叉树映射，线性映射比较)全部内容，希望文章能够帮你解决C++实现哈希映射(与map二叉树映射，线性映射比较)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---