데이터 구조: hashmap 원리

16649 단어 STL
이것 은 당신 에 게 hash 를 깊이 이해 하 게 하 는 절 입 니 다.맵 의 소개, 만약 당신 이 대 추 를 통째로 삼 키 고 싶 을 뿐, 그 원 리 를 이해 하고 싶 지 않다 면, 당신 은 오히려 이 절 을 생략 할 수 있 지만, 나 는 그래도 당신 에 게 좀 더 알 아 보 는 것 이 나 쁘 지 않다 고 건의 합 니 다.
hash_map 는 hash table (해시 표) 를 기반 으로 합 니 다.해시 표 의 가장 큰 장점 은 데이터 의 저장 과 찾기 소모 시간 을 크게 줄 이 고 거의 상수 시간 으로 볼 수 있다 는 것 이다.대 가 는 비교적 많은 메모 리 를 소모 하 는 것 에 불과 하 다.그러나 현재 메모리 가 점점 많아 지 는 상황 에서 공간 으로 시간 을 바 꾸 는 것 은 가치 가 있다.또 인 코딩 이 쉬 운 것 도 특징 이다.
그 기본 원 리 는 아래 표 시 된 범위 가 비교적 큰 배열 로 요 소 를 저장 하 는 것 이다.하나의 함수 (해시 함수, 해시 함수 라 고도 함) 를 설계 하여 모든 요소 의 키 워드 를 하나의 함수 값 (즉, 배열 아래 표시, hash 값) 과 대응 하 게 할 수 있 습 니 다. 그래서 이 배열 유닛 으로 이 요 소 를 저장 합 니 다.키워드 에 따라 모든 요소 로 '분류' 한 다음 에 이 요 소 를 해당 하 는 '클래스' 에 저장 하여 통 이 라 고 부 르 는 것 으로 간단하게 이해 할 수 있다.
그러나 각 요소 의 키워드 와 함수 값 이 일일이 대응 하 는 것 을 보장 할 수 없 기 때문에 서로 다른 요소 에 대해 똑 같은 함수 값 을 계산 할 가능성 이 높다. 그러면 '충돌' 이 생 긴 다. 다시 말 하면 서로 다른 요 소 를 똑 같은 '클래스' 로 나 누 는 것 이다.전체적으로 말 하면 '직접 주소 지정' 과 '충돌 해결' 은 하 쉬 표 의 두 가지 특징 이다.
hash_map, 우선 큰 메모 리 를 분배 하여 많은 통 을 형성 합 니 다.hash 함 수 를 이용 하여 키 를 다른 구역 (통) 에 비 추어 저장 합 니 다.그 삽입 과정 은:
  • 키 획득
  • hash 함 수 를 통 해 hash 값 얻 기
  • 통 번 호 를 받 습 니 다 (일반적으로 hash 값 으로 통 수 를 구 합 니 다)
  • 키 와 value 를 통 에 저장 합 니 다.

    • 그 수치 추출 과정 은:
  • 키 획득
  • hash 함 수 를 통 해 hash 값 얻 기
  • 통 번 호 를 받 습 니 다 (일반적으로 hash 값 으로 통 수 를 구 합 니 다)
  • 통 의 내부 요소 가 key 와 같 는 지 비교 하고 모두 같 지 않 으 면 찾 지 못 했다.
  • 같은 기록 의 value 를 꺼낸다.

    • hash_map 에서 직접 주 소 는 hash 함수 로 생 성 되 고 충돌 을 해결 하 며 비교 함수 로 해결 합 니 다.각 통 내부 에 하나의 요소 만 있다 면 찾 을 때 한 번 만 비교 한 다 는 것 을 알 수 있다.많은 통 안에 값 이 없 을 때, 많은 조회 가 더욱 빨 라 질 것 이다.
    이 를 통 해 알 수 있 듯 이 해시 표를 실현 하려 면 사용자 와 관련 된 것 은 hash 함수 와 비교 함수 입 니 다.이 두 매개 변 수 는 마침 우리 가 hash 를 사용 하고 있 는 것 이다.map 에서 지정 한 인자 가 필요 합 니 다.
    2 hash_map 사용
    2.1 간단 한 실례
    서 두 르 지 마 세 요.map 에 따 르 면 우 리 는 먼저 간단 한 예 를 보 겠 습 니 다. 랜 덤 으로 ID 번호 와 ID 번호 에 해당 하 는 정 보 를 드 리 겠 습 니 다. ID 번호 의 범 위 는 1 ~ 2 의 31 번 입 니 다.검색 을 빠르게 저장 하 는 방법 입 니 다.
    #include 
#include 
using namespace std;
int main(){
hash_map<int, string> mymap;
mymap[9527]="      ";
mymap[1000000]="       ";
mymap[10000]="       ";
...
if(mymap.find(10000) != mymap.end()){
...
}
    够简单，和map使用方法一样。这时你或许会问？hash函数和比较函数呢？不是要指定么？你说对了，但是在你没有指定hash函数和比较函数的时候，你会有一个缺省的函数，看看hash_map的声明，你会更加明白。下面是SGI STL的声明： 
    template <class _Key, class _Tp, class _HashFcn = hash<_key>,
class _EqualKey = equal_to<_key>,
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class hash_map
{
...
}
    也就是说，在上例中，有以下等同关系： 
    ...
hash_map<int, string> mymap;
//   :
hash_map<int, string, hash<int>, equal_to<int> > mymap;
    Alloc我们就不要取关注太多了(希望深入了解Allocator的朋友可以参看 标准库 STL ：Allocator能做什么 )

    2.2 hash_map 的hash函数

    hash< int>到底是什么样子？看看源码: 
    struct hash<int> {
size_t operator()(int __x) const { return __x; }
};
    原来是个函数对象。在SGI STL中，提供了以下hash函数： 
    struct hash<char*>
struct hash<const char*>
struct hash<char>
struct hash<unsigned char>
struct hash<signed char>
struct hash<short>
struct hash<unsigned short>
struct hash<int>
struct hash<unsigned int>
struct hash<long>
struct hash<unsigned long>
    也就是说，如果你的key使用的是以上类型中的一种，你都可以使用缺省的hash函数。当然你自己也可以定义自己的hash函数。对于自定义变量，你只能如此，例如对于string，就必须自定义hash函数。例如： 
    struct str_hash{
size_t operator()(const string& str) const
{
unsigned long __h = 0;
for (size_t i = 0 ; i < str.size() ; i ++)
__h = 5*__h + str[i];
return size_t(__h);
}
};
//               hash  ，      ：
struct str_hash{
size_t operator()(const string& str) const
{
return return __stl_hash_string(str.c_str());
}
};
    在声明自己的哈希函数时要注意以下几点：
    1. 使用struct，然后重载operator().
    2. 返回是size_t
    3. 参数是你要hash的key的类型。
    4. 函数是const类型的。
    如果这些比较难记，最简单的方法就是照猫画虎，找一个函数改改就是了。

    现在可以对开头的"岳不群"进行哈希化了  . 直接替换成下面的声明即可：

    map namemap;
//  ：
hash_map namemap;
    其他用法都不用边。当然不要忘了吧str_hash的声明以及头文件改为hash_map。

    你或许会问：比较函数呢？别着急，这里就开始介绍hash_map中的比较函数。

    2.3 hash_map 的比较函数

    在map中的比较函数，需要提供less函数。如果没有提供，缺省的也是less< Key> 。在hash_map中，要比较桶内的数据和key是否相等，因此需要的是是否等于的函数:equal_to< Key> 。先看看equal_to的源码： 
    //      SGI STL
//   binary_function     ，            。
template <class _Arg1, class _Arg2, class _Result>
struct binary_function {
typedef _Arg1 first_argument_type;
typedef _Arg2 second_argument_type;
typedef _Result result_type;
};
//  equal_to   ：
template <class _Tp>
struct equal_to : public binary_function<_tp>bool>
{
bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
};
    如果你使用一个自定义的数据类型，如struct mystruct, 或者const char* 的字符串，如何使用比较函数？使用比较函数，有两种方法. 第一种是：重载==操作符，利用equal_to;看看下面的例子： 
    struct mystruct{
int iID;
int  len;
bool operator==(const mystruct & my) const{
return (iID==my.iID) && (len==my.len) ;
}
};
    这样，就可以使用equal_to< mystruct>作为比较函数了。另一种方法就是使用函数对象。自定义一个比较函数体： 
    struct compare_str{
bool operator()(const char* p1, const char*p2) const{
return strcmp(p1,p2)==0;
}
};
    有了compare_str，就可以使用hash_map了。 
    typedef hash_map<const char*, string, hash<const char*>, compare_str> StrIntMap;
StrIntMap namemap;
namemap["   "]="      ，     ";
namemap["   "]="     ，      ";
namemap["    "]="    ，    ";

    2.4 hash_map 函数

    hash_map的函数和map的函数差不多。具体函数的参数和解释，请参看： STL 编程手册：Hash_map ，这里主要介绍几个常用函数。
    1. hash_map(size_type n) 如果讲究效率，这个参数是必须要设置的。n 主要用来设置hash_map 容器中hash桶的个数。桶个数越多，hash函数发生冲突的概率就越小，重新申请内存的概率就越小。n越大，效率越高，但是内存消耗也越大。
    2. const_iterator find(const key_type& k) const. 用查找，输入为键值，返回为迭代器。
    3. data_type& operator[](const key_type& k) . 这是我最常用的一个函数。因为其特别方便，可像使用数组一样使用。不过需要注意的是，当你使用[key ]操作符时，如果容器中没有key元素，这就相当于自动增加了一个key元素。因此当你只是想知道容器中是否有key元素时，你可以使用find。如果你希望插入该元素时，你可以直接使用[]操作符。
    4. insert 函数。在容器中不包含key值时，insert函数和[]操作符的功能差不多。但是当容器中元素越来越多，每个桶中的元素会增加，为了保证效率，hash_map会自动申请更大的内存，以生成更多的桶。因此在insert以后，以前的iterator有可能是不可用的。
    5. erase 函数。在insert的过程中，当每个桶的元素太多时，hash_map可能会自动扩充容器的内存。但在sgi stl中是erase并不自动回收内存。因此你调用erase后，其他元素的iterator还是可用的。

    3 相关hash容器

    hash 容器除了hash_map之外，还有hash_set, hash_multimap, has_multiset, 这些容器使用起来和set, multimap, multiset的区别与hash_map和map的区别一样，我想不需要我一一细说了吧。

    4 其他

    这里列几个常见问题，应该对你理解和使用hash_map比较有帮助。

    4.1 hash_map和map的区别在哪里？

    • 构造函数。hash_map需要hash函数，等于函数；map只需要比较函数(小于函数).
    • 存储结构。hash_map采用hash表存储，map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。

    4.2 什么时候需要用hash_map，什么时候需要用map?

    总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且hash_map的构造速度较慢。

    现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。

    这里还有个关于hash_map和map的小故事，看看:http://dev.csdn.net/Develop/article/14/14019.shtm

    4.3 如何在hash_map中加入自己定义的类型?

    你只要做两件事, 定义hash函数，定义等于比较函数。下面的代码是一个例子： 
    -bash-2.05b$ cat my.cpp
#include 
#include 
#include 
using namespace std;
//define the class
class ClassA{
public:
ClassA(int a):c_a(a){}
int getvalue()const { return c_a;}
void setvalue(int a){c_a;}
private:
int c_a;
};
//1 define the hash function
struct hash_A{
size_t operator()(const class ClassA & A)const{
//  return  hash(classA.getvalue());
return A.getvalue();
}
};
//2 define the equal function
struct equal_A{
bool operator()(const class ClassA & a1, const class ClassA & a2)const{
return  a1.getvalue() == a2.getvalue();
}
};
int main()
{
hash_map hmap;
ClassA a1(12);
hmap[a1]="I am 12";
ClassA a2(198877);
hmap[a2]="I am 198877";
cout<return 0;
}
-bash-2.05b$ make my
c++  -O -pipe -march=pentiumpro  my.cpp  -o my
-bash-2.05b$ ./my
I am 12
I am 198877
     
  
    typedef map KeyMap;
     
  
    当你希望使用hash_map来替换的时候，只需要修改:
     
  
     
     
  
    typedef hash_map KeyMap;
      
    다른 것 은 기본적으로 변 하지 않 는 다.물론 키 형식의 hash 함수 와 비교 함수 가 있 는 지 주의해 야 합 니 다.
    【 템 플 릿 】 피리 칼 나무
    RDB 와 No-SQL

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage