STL---hash_map 소개 및 대량의 데이터 처리

1. hash맵 소개
hash_map 의 용법 은 map 와 같 습 니 다. insert, size, count 등 동작 을 제공 하고 안의 요소 도 pair 형식 으로 저 장 됩 니 다.외부 에서 제공 하 는 함수 와 데이터 형식 은 일치 하지만 그 밑바닥 의 실현 은 완전히 다르다. 맵 밑바닥 의 데이터 구 조 는 rb 이다.tree, 붉 은 검 은 나무 가 질서 가 있 고 매번 작업 의 복잡 도 는 logN 에 안정 적 입 니 다.한 쉬map 는 해시 표 (hashtable) 로 이 루어 집 니 다. hash 함수 가 적당 한 경우 빠 른 조회 속도 O (1) 를 제공 할 수 있 습 니 다. hash 함수 가 썩 으 면 hash 를 사용 합 니 다.map, 재난 이 될 것 입 니 다. 작업 복잡 도가 최 악 이면 O (N) 에 도착 합 니 다.
예:

int main()
{
    hash_map<int, string> hmap;//      

    //  
    hmap.insert(pair<int, string>(15, "tom"));//    pair  
    hmap.insert(hash_map<int,string>::value_type(24, "jerry"));//value_type  pair   
    hmap[53]="simth";
    hmap[14]="john";
    hamp[-1]="henry";

    //         
    hash_map<int, string>::iterator it=hmap.begin();

    while(it != hmap.end())
    {//    
        cout<first<<" "<second<23);//  
    if(it!=hmap.end())
        PRINT(it);
    cout<cout<58)<cout<int,string>::const_reverse_iterator cit = hmap.rend();
    PRINT(cit);
    return 0;
}

2. map 와 hash지도 비교
전체적으로 말 하면 hashmap 검색 속 도 는 map 보다 빠 르 고 검색 속 도 는 기본적으로 데이터 크기 와 상 관 없 이 상수 단계 에 속 합 니 다.맵 의 검색 속 도 는 log (n) 단계 입 니 다.hash 그리고 hash 함수 의 시간 소모.100 w 의 기록 이 있 을 때 맵 도 20 번 의 비교 만 필요 하고 200 w 도 21 번 의 비교 만 필요 합 니 다!그래서 반드시 상수 가 log (n) 보다 작은 것 은 아니다!
hash_map 는 공간 에 대한 요구 가 map 보다 훨씬 높 기 때문에 공간 으로 시간 을 바 꾸 는 방법 입 니 다. 그리고 hashmap hash 함수 와 hash 인자 선택 이 좋 지 않 으 면 원 하 는 효과 에 이 르 지 못 할 수도 있 으 므 로 map 를 사용 하 는 지 hashmap, 세 가지 측면 에서 저울질: 속도, 데이터 양, 메모리 사용, 그리고 하 나 는 당신 의 경험 입 니 다!특별한 기준 은 없다.
또한 다시 쓰 기 를 통 해 hashcopair 모방 함수, 통 수량 에 대한 정 의 를 변경 합 니 다. 값 이 적당 하면 더 좋 은 성능 을 얻 을 수 있 습 니 다.그리고 데이터 가 사용자 정의 형식 이 라면 이 모방 함 수 를 다시 써 야 합 니 다.원래 의 문법 을 모방 할 수 있 습 니 다. 모든 구성원 함수, 구성원 변 수 는 하나 도 없어 서 는 안 됩 니 다!
3. hashmap 와 hashtable 비교
HashTable 의 응용 은 매우 광범 위 합 니 다. HashMap 은 새로운 프레임 워 크 에서 HashTable 을 대체 하 는 클래스 입 니 다. 즉, HashMap 을 사용 하고 HashTable 을 사용 하지 않 는 것 을 권장 합 니 다.Hash Table 이 좋다 고 생각 하 시 나 봐 요. 왜 안 쓰 세 요?여기 서 그들의 차 이 를 간단하게 분석 하 다.
1. HashTable 의 방법 은 동기 화 되 어 있 습 니 다. HashMap 은 동기 화 되 지 않 았 기 때문에 다 중 스 레 드 장소 에서 HashMap 을 수 동 으로 동기 화 해 야 합 니 다. 이 차 이 는 Vector 와 Array List 와 같 습 니 다.
2. HashTable 은 null 값 (key 와 value 모두 안 됨) 을 허용 하지 않 으 며, HashMap 은 null 값 (key 와 value 모두 가능) 을 허용 합 니 다.
3. HashTable 에는 contains (Object value) 기능 이 있 습 니 다. contains Value (Object value) 기능 과 같 습 니 다.
4. HashTable 은 Enumeration, HashMap 은 Iterator 를 사용한다.
이상 은 표면적 인 차이 일 뿐 그들의 실현 도 크게 다르다.
5. HashTable 에서 hash 배열 의 기본 크기 는 11 이 고 증가 하 는 방식 은 old * 2 + 1 입 니 다.HashMap 에서 hash 배열 의 기본 크기 는 16 이 고 반드시 2 의 지수 입 니 다.
6. 해시 값 의 사용 에 따라 HashTable 은 대상 의 hashCode 를 직접 사용 합 니 다. 코드 는 다음 과 같 습 니 다.

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

그리고 HashMap 은 hash 값 을 다시 계산 하고 모델 을 대체 합 니 다.

int hash = hash(k);
int i = indexFor(hash, table.length);

static int hash(Object x) {
　　int h = x.hashCode();

　　h += ~(h << 9);
　　h ^= (h >>> 14);
　　h += (h << 4);
　　h ^= (h >>> 10);
　　return h;
}
static int indexFor(int h, int length) {
　　return h & (length-1);
}

이상 은 단지 비교적 두 드 러 진 차이 일 뿐, 물론 그들의 실현 에는 많은 차이 가 있다.
4. 왜 hashmap
map 의 검색 속 도 는 log 2 (n) 등급 이 고 100 만 개의 기록 이 며 최대 20 번 의 string. copare 를 비교 하면 찾 으 려 는 기록 을 찾 을 수 있 습 니 다.200 만 건의 기록 도 21 번 의 비교 만 하면 된다.
속 도 는 영원히 현실 의 수 요 를 만족 시 킬 수 없다.100 만 건의 기록 이 있다 면 검색 을 자주 해 야 할 때 20 번 의 비교 도 병목 이 될 수 있 습 니 다. 한 번 또는 두 번 의 비교 로 내 려 갈 수 있다 면 가능 합 니까?그리고 기록 이 200 만 까지 셀 때 도 한 번 또는 두 번 의 비교 가 가능 할 까?그리고 맵 과 같은 편리 한 사용 이 필요 합 니 다.
답 은 긍정 적 이다.이때 당신 은 has 가 필요 합 니 다.map. hashmap 는 현재 C + + 표준 템 플 릿 라 이브 러 리 에 포함 되 지 않 았 으 나 거의 모든 버 전의 STL 이 해당 하 는 실현 을 제공 합 니 다.응용 도 광범 위 하 다.본 격 적 으로 hash 사용 중map 전에 hash맵 의 원리.
hash_map 원리
hash_map 는 hash table (해시 표) 를 기반 으로 합 니 다.해시 표 의 가장 큰 장점 은 데이터 의 저장 과 찾기 소모 시간 을 크게 줄 이 고 거의 상수 시간 으로 볼 수 있다 는 것 이다.대 가 는 비교적 많은 메모 리 를 소모 하 는 것 에 불과 하 다.그러나 현재 메모리 가 점점 많아 지 는 상황 에서 공간 으로 시간 을 바 꾸 는 것 은 가치 가 있다.또 인 코딩 이 쉬 운 것 도 특징 이다.
그 기본 원 리 는:

                   。        （    ，      
 ），                 （     ，hash ）   ，       
         ；         ，           “  ”，       
     “ ”      ，   。

그러나 각 요소 의 키워드 와 함수 값 이 일일이 대응 하 는 것 을 보장 할 수 없 기 때문에 서로 다른 요소 에 대해 똑 같은 함수 값 을 계산 할 가능성 이 높다. 그러면 '충돌' 이 생 긴 다. 다시 말 하면 서로 다른 요 소 를 똑 같은 '클래스' 로 나 누 는 것 이다.전체적으로 말 하면 '직접 주소 지정' 과 '충돌 해결' 은 하 쉬 표 의 두 가지 특징 이다.
hash_map, 우선 큰 메모 리 를 분배 하여 많은 통 을 형성 합 니 다.hash 함 수 를 이용 하여 키 를 다른 구역 (통) 에 비 추어 저장 합 니 다.그 삽입 과정 은:

（1）  key
（2）  hash    hash 
（3）    (    hash      )
（4）  key value   。

그 수치 추출 과정 은:

（1）  key
（2）  hash    hash 
（3）    (    hash      )
（4）           key  ，     ，     。
（5）        value。

hash_map 에서 직접 주 소 는 hash 함수 로 생 성 되 고 충돌 을 해결 하 며 비교 함수 로 해결 합 니 다.각 통 내부 에 하나의 요소 만 있다 면 찾 을 때 한 번 만 비교 한 다 는 것 을 알 수 있다.많은 통 안에 값 이 없 을 때, 많은 조회 가 더욱 빨 라 질 것 이다.
이 를 통 해 알 수 있 듯 이 해시 표를 실현 하려 면 사용자 와 관련 된 것 은 hash 함수 와 비교 함수 입 니 다.이 두 매개 변 수 는 마침 우리 가 hash 를 사용 하고 있 는 것 이다.map 에서 지정 한 인자 가 필요 합 니 다.
5. 대량의 데이터 처리
질문:
천만 개의 문자 메시지 가 있 고 중복 되 며 텍스트 파일 로 저장 되 며 한 줄 한 줄 반복 되 어 있 습 니 다.5 분 동안 가장 많이 반복 되 는 10 가 지 를 찾 아 보 세 요.
분석: 일반적인 방법 은 먼저 순 서 를 매 겨 한 번 훑 어보 고 가장 많이 중복 되 는 10 가 지 를 찾 는 것 이다.그러나 정렬 알고리즘 의 복잡 도 는 nlgn 이 가장 낮다.hash 를 설계 할 수 있 습 니 다.table, hash_map < string, int >, 순서대로 천만 개의 문 자 를 읽 고 hash 로 불 러 옵 니 다.table 표 에 서 는 중복 횟수 를 집계 하 는 동시에 최대 10 개의 문자 표를 유지 합 니 다.
이렇게 한 번 훑 어보 면 가장 많은 상위 10 개 를 찾 을 수 있 고 알고리즘 의 복잡 도 는 O (n) 이다.