STL 관련 용기 값 hashtable

hashtable (산 목록) 은 데이터 구조 로 요소 의 삽입, 삭제, 검색 작업 에 있어 상수 평균 시간 복잡 도 O (1) 가 있 습 니 다.
hashtable 명사
해시 함수: 특정한 요 소 를 색인 으로 표시 합 니 다.충돌 (collision): 서로 다른 요소 가 같은 위치 에 매 핑 됩 니 다.충돌 해결 방법: 선형 탐색 법, 2 차 탐색 법, 체인 열기 등.부하 계수: 요소 개 수 를 표 크기 로 나 눕 니 다.주 그룹: 평균 삽입 원가 의 성장 폭 은 부하 계수 의 성장 폭 보다 훨씬 높다.차 그룹: hashtable 이 2 차 탐 사 를 사용 하면 두 요소 가 hash function 을 통 해 계 산 된 위치 가 같 으 면 삽입 할 때 탐색 하 는 위치 도 같 고 어떤 낭 비 를 초래 합 니 다.체인 열기: 표 요소 마다 list 가 있 습 니 다.통 (bucket): hashtable 표 의 모든 요소 입 니 다.
hashtable 조직 방식
노드 클래스

template 
struct _Hashtable_node
{
  _Hashtable_node* _M_next;
  _Val _M_val;
};  

hashtable 의 노드 는 list 노드 와 유사 합 니 다.하나의 Node 지침 은 모든 통 의 목록 의 첫 번 째 요 소 를 가리 키 며, 통 의 링크 의 첫 번 째 주 소 는 vector 벡터 에 저 장 됩 니 다.

typedef _Hashtable_node<_val> _Node;
vector<_node> _M_buckets;

hashtable 교체 기의 자체 증가 연산 자 정 의 는 다음 과 같 습 니 다.

template 
_Hashtable_iterator<_val>&
_Hashtable_iterator<_val>::operator++()
{
  const _Node* __old = _M_cur;      //       
  _M_cur = _M_cur->_M_next;         //      
  if (!_M_cur) {                    //         ，            
    //            
    size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
    //    ，          ，       
    while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
        //                   
      _M_cur = _M_ht->_M_buckets[__bucket];    
  }
  return *this;
}

hashtable 클래스 는 다섯 개의 템 플 릿 매개 변 수 를 정의 합 니 다.

template 
class hashtable;

_Val 값 유형키 키 종류HashFcn 해시 함수ExtractKey 추출 키 의 방법EqualKey 판단 키 가 같은 방법Alloc 분배 기 종류
hashtable 삽입 동작
insert_unique 는 값 이 중복 되 는 삽입 을 허용 하지 않 습 니 다:

 pair insert_unique(const value_type& __obj)
  {
    resize(_M_num_elements + 1);
    return insert_unique_noresize(__obj);
  }

이 함 수 는 먼저 resize 함 수 를 호출 하여 현재 요소 에 1 의 값 을 추가 하여 확장 이 필요 한 지 확인 합 니 다.처리 완료 후 치obj 를 hashtable 에 삽입 합 니 다.resize 함수 의 정 의 는 다음 과 같 습 니 다.

template 
void hashtable<_val>
  ::resize(size_type __num_elements_hint)
{
  const size_type __old_n = _M_buckets.size();    //      
  if (__num_elements_hint > __old_n) {            //         
    //                __n
    const size_type __n = _M_next_size(__num_elements_hint);
    if (__n > __old_n) {                          //          ：    
      //     __n（    ）      
      vector<_node _all=""> __tmp(__n, (_Node*)(0),
                                 _M_buckets.get_allocator());
      __STL_TRY {
        //  hashtable     
        for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
          _Node* __first = _M_buckets[__bucket];        //         
          while (__first) {                             //           
            //              _M_val，      __n，
            //      hashtable     （rehash）
            size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
            //              ，             
            _M_buckets[__bucket] = __first->_M_next;
            
            //             ，       。
            //           hashtable              
            __first->_M_next = __tmp[__new_bucket];
            // hashtable，         __first
            __tmp[__new_bucket] = __first;

            //  __first    __first->_M_next，   hashtable             。
            __first = _M_buckets[__bucket];          
          }
        }
        //  hashtable       hash      
        _M_buckets.swap(__tmp);    //              。
        //       __tmp   ，       ，__tmp        ，         。
      }
      //             
#         ifdef __STL_USE_EXCEPTIONS
      catch(...) {
        //           
        for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
          //          
          while (__tmp[__bucket]) {
            _Node* __next = __tmp[__bucket]->_M_next;
            _M_delete_node(__tmp[__bucket]);    //      
            __tmp[__bucket] = __next;           //      
          }
        }
        throw;
      }
#         endif /* __STL_USE_EXCEPTIONS */
    }
  }
}

insert_unique_noresize 의 함수 정 의 는 다음 과 같 습 니 다.

template 
pair::iterator, bool> 
hashtable<_val>
  ::insert_unique_noresize(const value_type& __obj)
{
  const size_type __n = _M_bkt_num(__obj);     //         ，      
  _Node* __first = _M_buckets[__n];            //       
    
  //      ，     
  for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 
    //      __obj      
    if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
      //           ，         。  
      return pair(iterator(__cur, this), false);
  
  //                ，  
  _Node* __tmp = _M_new_node(__obj);    //       
  __tmp->_M_next = __first;             //             
  _M_buckets[__n] = __tmp;              //                 
  ++_M_num_elements;                    //  hashtable    
  //          ，         。
  return pair(iterator(__tmp, this), true);
}

결합 insert유 니 크 함수 에서 호출 된 두 함수 인터페이스의 분석 을 통 해 알 수 있 듯 이:

insert 진행 중유 니 크 함수 가 실 행 될 때 먼저 통 벡터 를 확대 한 다음 hashtable 에 요 소 를 삽입 합 니 다.

hashtable 의 확장 작업 은 vector 의 자체 성장 과정 과 유사 하 며 모두 1. 더 큰 공간 을 신청 합 니 다.2. 원래 용기 의 데 이 터 를 새로운 용기 로 옮 기기;3. 원래 용기 의 공간 청소 하기;3 부작.

vector 용기 의 자체 성장 과 달리 데이터 이전 과정 에서 hashtable 은 새로운 통 수량 에 따라 데 이 터 를 다시 매 핑 해 야 합 니 다.

insert_equal 중복 삽입 허용:

  iterator insert_equal(const value_type& __obj)
  {
    resize(_M_num_elements + 1);
    return insert_equal_noresize(__obj);
  }

insert유 니 크 비교, 함수 확장 후 중복 값 을 허용 하 는 비 확장 삽입 함수 insert 호출equal_noresize：

template 
typename hashtable<_val>::iterator 
hashtable<_val>
  ::insert_equal_noresize(const value_type& __obj)
{
  const size_type __n = _M_bkt_num(__obj);        //         ，      
  _Node* __first = _M_buckets[__n];               //        

  ///      ，       
  for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 
    //      __obj      ，          
    if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {
      _Node* __tmp = _M_new_node(__obj);        //       
      __tmp->_M_next = __cur->_M_next;          //                   
      __cur->_M_next = __tmp;                   //              
      ++_M_num_elements;                        //      
      return iterator(__tmp, this);             //      ，  
    }
    
  //                
  _Node* __tmp = _M_new_node(__obj);            //       
  __tmp->_M_next = __first;                     //             
  _M_buckets[__n] = __tmp;                      //               
  ++_M_num_elements;                            //      
  return iterator(__tmp, this);                 //      ，  
}

insert_unique_noresize 와 insertequal_noresize 의 비교:

insert_unique_noresize 는 hashtable 의 한 통 에서 삽입 값 과 같은 노드 를 찾 습 니 다. 찾 으 면 바로 되 돌아 가 삽입 에 실 패 했 습 니 다.그렇지 않 으 면 통 의 링크 의 머리 에 새 노드 를 삽입 합 니 다.

insert_equal_noresize 는 hashtable 의 한 통 에서 삽입 값 과 같은 노드 를 찾 고 찾 으 면 그 다음 에 새 노드 를 삽입 합 니 다.그렇지 않 으 면 통 의 링크 의 머리 에 새 노드 를 삽입 합 니 다.hashtable 삭제 및 복사

hashtable 삭제

template 
void hashtable<_val>::clear()
{
  //       
  for (size_type __i = 0; __i < _M_buckets.size(); ++__i) {
    _Node* __cur = _M_buckets[__i];    //   
    while (__cur != 0) {               //       
      _Node* __next = __cur->_M_next;  //          
      _M_delete_node(__cur);           //          ，      
      __cur = __next;                  //    
    }
    _M_buckets[__i] = 0;               //        
  }
  _M_num_elements = 0;                 //       0   
}

hashtable 복사

template 
void hashtable<_val>
  ::_M_copy_from(const hashtable& __ht)
{
  _M_buckets.clear();            //      
  _M_buckets.reserve(__ht._M_buckets.size());    //          ，           
  //                
  _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
  __STL_TRY {
    //   
    for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
      const _Node* __cur = __ht._M_buckets[__i];    //     （   ）         
      if (__cur) {                                  //    
        _Node* __copy = _M_new_node(__cur->_M_val); //             
        _M_buckets[__i] = __copy;                   //               

        for (_Node* __next = __cur->_M_next;        //         ，   
             __next; 
             __cur = __next, __next = __cur->_M_next) {
          __copy->_M_next = _M_new_node(__next->_M_val); //      
          __copy = __copy->_M_next;                      //        
        }
      }
    }
    _M_num_elements = __ht._M_num_elements;              //        
  }
  __STL_UNWIND(clear());                                 //              
}

작은 매듭

hashtable 은 요소 의 임 의 성에 의존 하지 않 고 요소 가 상대 적 으로 고정된 범위 에 분포 되 어 있다 고 가정 하면 사전 구조 와 유사 하 다.

hashtable 은 상수 복잡 도의 삽입, 삭제, 검색 작업 을 제공 할 수 있 으 나 해시 표를 만들어 야 하 며 공간의 대가 로 시간 을 바 꾸 는 효율 적 입 니 다.

트 리 구 조 는 시간 복잡 도 에 대한 요소 검색 작업 을 제공 하고 요소 의 임 의 성에 의존 합 니 다.