flyonok

统计

留言簿(8)

ACE

book

boost

bsd

c study

c++

code download

codeblock

computer clound

Eclipse

embed system

erlang

ET++

gtk

ic card

java

KDE

libevent

linux

linux--MM

mysql

network education

one card

oracle

pcap relation

php

powerbuilder

python

QT

software config

software test

SQL server

UML

wireless

wxwidgets

陈宾

阅读排行榜

评论排行榜

open addressing--hash table

1 Overview

      Open addressing和Chaining是两种不同的解决hash冲突的策略。当多个不同的key被映射到相同的slot时,chaining方式采用链表保存所有的value。而Open addressing则尝试在该slot的邻近位置查找,直到找到对应的value或者空闲的slot, 这个过程被称作probing。常见的probing策略有Linear probing,Quadratic probing和Double hashing。

 

2 Chaining

2.1 Chaining in java.util.HashMap

      在分析open addressing策略之前,首先简单介绍一下大多数的Java 核心集合类采用的chaining策略,以便比较。 java.util.HashMap有一个Entry[]类型的成员变量table,其每个非null元素都是一个单向链表的表头。

  • put():如果存在hash冲突,那么对应的table元素的链表长度会大于1。
  • get():需要对链表进行遍历,在遍历的过程中不仅要判断key的hash值是否相等,还要判断key是否相等或者equals。
  • 对于put()和get()操作,如果其参数key为null,那么HashMap会有些特别的优化。

      Chaining策略的主要缺点是需要通过Entry保存key,value以及指向链表下个节点的引用(Map.Entry就有四个成员变量),这意味着更多的内存使用(尤其是当key,value本身使用的内存很小时,额外使用的内存所占的比例就显得比较大)。此外链表对CPU的高速缓存不太友好。

 

3 Open Addressing

3.1 Probing

3.1.1 Linear probing

      两次查找位置的间隔为一固定值,即每次查找时在原slot位置的基础上增加一个固定值(通常为1),例如:P = (P + 1) mod SLOT_LENGTH。其最大的优点在于计算速度快,另外对CPU高速缓存更友好。其缺点也非常明显:

      假设key1,key2,key3的hash code都相同并且key1被映射到slot(p),那么在计算key2的映射位置时需要查找slot(p), slot(p+1),计算key3的映射位置时需要查找slot(p), slot(p+1),slot(p+2)。也就是说对于导致hash冲突的所有key,在probing过程中会重复查找以前已经查找过的位置,这种现象被称为clustering。

 
3.1.2 Quadratic probing

      两次查找位置的间隔线性增长,例如P(i) = (P + c1*i + c2*i*i) mod SLOT_LENGTH,其中c1和c2为常量且c2不为0(如果为0,那么降级为Linear probing)。 Quadratic probing的各方面性能介于Linear probing和Double hashing之间。


3.1.3 Double hashing 
       两次查找位置的间隔为一固定值,但是该值通过另外一个hash算法生成,例如P = (P + INCREMENT(key)) mod SLOT_LENGTH,其中INCREMENT即另外一个hash算法。以下是个简单的例子:

      H(key) = key mod 10
      INCREMENT(key) = 1 + (key mod 7)
      P(15): H(15) = 5;
      P(35): H(35) = 5, 与P(15)冲突,因此需要进行probe,位置是 (5 + INCREMENT(35)) mod 10 = 6
      P(25): H(25) = 5, 与P(15)冲突,因此需要进行probe,位置是 (5 + INCREMENT(25)) mod 10 = 0

      P(75): H(75) = 5, 与P(15)冲突,因此需要进行probe,位置是 (5 + INCREMENT(75)) mod 10 = 1

      从以上例子可以看出,跟Linear probing相比,减少了重复查找的次数。

 

3.2 Load Factor

      基于open addressing的哈希表的性能对其load factor属性值非常敏感。如果该值超过0.7 (Trove maps/sets的默认load factor是0.5),那么性能会下降的非常明显。由于hash冲突导致的probing次数跟(loadFactor) / (1 - loadFactor)成正比。当loadFactor为1时,如果哈希表中的空闲slot非常少,那么可能会导致probing的次数非常大。

 

3.3 Open addressing in gnu.trove.THashMap

      GNU Trove (http://trove4j.sourceforge.net/) 是一个Java 集合类库。在某些场景下,Trove集合类库提供了更好的性能,而且内存使用更少。以下是Trove中跟open addressing相关的几个特性:

  • Trove maps/sets没有使用chaining解决hash冲突,而是使用了open addressing。
  • 跟chaining相比,open addressing对hash算法的要求更高。通过TObjectHashingStrategy 接口, Trove支持定制hash算法(例如不希望使用String或者数组的默认hash算法)。
  • Trove提供的maps/sets的capaicity属性一定是质数,这有助于减少hash冲突。
  • 跟java.util.HashSet不同,Trove sets没有使用maps,因此不需要额外分配value的引用。

      跟java.util.HashMap相比,gnu.trove.THashMap没有Entry[] table之类的成员变量,而是分别通过Object[] _set,V[] _values直接保存key和value。在逻辑上,Object[] _set中的每个元素都有三种状态:

  • FREE:该slot目前空闲;
  • REMOVED:该slot之前被使用过,但是目前数据已被移除;
  • OCCUPIED:该slot目前被使用中;

      这三种状态的迁移过程如下:

  • 在构造或者resize时,所有_set元素都会赋值为FREE(FREE状态);
  • 向THashMap中put某个key/value对时,_set中对应的元素会被赋值为put()方法的参数key(OCCUPIED状态);
  • 从THashMap中以key进行remove的时,_set中对应的元素会被赋值为REMOVED(注意:不是赋值为FREE); 

      以下是关于状态迁移的简单例子(:= 的含义是赋值, H(key) = key mod 11):

  • put(7, value):  _set[7] := 7;
  • put(9, value):  _set[9] := 9;
  • put(18, value):  由于_set[7]处于OCCUPIED状态,导致hash冲突;假设第一次probe计算得出9,由于_set[9]处于OCCUPIED状态,仍然hash冲突; 假设再次probe计算得到1, 由于_set[1]处于FREE状态,所以_set[1] := 18;
  • get(18): _set[7]处于OCCUPIED状态并且与18不等;假设第一次probe计算得出9,_set[9]的值与18不等;假设再次probe计算得到1, 由于_set[1] 的值等于18,所以返回对应value;
  • remove(9): _set[9] := REMOVED;
  • get(18): _set[7]的值与18不等;假设第一次probe计算得出9,由于_set[9]状态为REMOVED,需要再次probe;假设再次probe计算得到1, 由于_set[1] 的值等于18,所以返回对应value;
  • put(9, value):  _set[9] := 9;

      以下是与get()方法相关的代码片段:

Java代码 
  1. public V get(Object key) {  
  2.     int index = index((K) key);  
  3.     return index < 0 ? null : _values[index];  
  4. }  
  5.   
  6. protected int index(T obj) {  
  7.     final TObjectHashingStrategy<T> hashing_strategy = _hashingStrategy;  
  8.   
  9.     final Object[] set = _set;  
  10.     final int length = set.length;  
  11.     final int hash = hashing_strategy.computeHashCode(obj) & 0x7fffffff;  
  12.     int index = hash % length;  
  13.     Object cur = set[index];  
  14.   
  15.     if ( cur == FREE ) return -1;  
  16.   
  17.     // NOTE: here it has to be REMOVED or FULL (some user-given value)  
  18.     if ( cur == REMOVED || ! hashing_strategy.equals((T) cur, obj)) {  
  19.         // see Knuth, p. 529  
  20.         final int probe = 1 + (hash % (length - 2));  
  21.   
  22.         do {  
  23.             index -= probe;  
  24.             if (index < 0) {  
  25.                 index += length;  
  26.             }  
  27.             cur = set[index];  
  28.         } while (cur != FREE  
  29.              && (cur == REMOVED || ! _hashingStrategy.equals((T) cur, obj)));  
  30.     }  
  31.   
  32.     return cur == FREE ? -1 : index;  
  33. }  

      从以上代码可以看出get()方法的流程如下, 根据key的hash值找到对应的set元素,判断是否存在hash冲突。

      如果不存在hash冲突,那么该set元素的可能状态如下:

  • FREE:意味着THashMap中不存在该key;
  • OCCUPIED,并且该元素的值等于get()方法的参数key:意味着THashMap中存在该key;
  • 非以上两种情况:意味着存在hash冲突,需要进行probe,直到找到状态为以上两种状态的set元素;

      以下是与put()方法相关的代码片段:

Java代码 
  1. public V put(K key, V value) {  
  2.     int index = insertionIndex(key);  
  3.     return doPut(key, value, index);  
  4. }  
  5.   
  6. private V doPut(K key, V value, int index) {  
  7.     V previous = null;  
  8.     Object oldKey;  
  9.     boolean isNewMapping = true;  
  10.     if (index < 0) {  
  11.         index = -index -1;  
  12.         previous = _values[index];  
  13.         isNewMapping = false;  
  14.     }  
  15.     oldKey = _set[index];  
  16.     _set[index] = key;  
  17.     _values[index] = value;  
  18.     if (isNewMapping) {  
  19.         postInsertHook(oldKey == FREE);  
  20.     }  
  21.   
  22.     return previous;  
  23. }  
  24.   
  25. protected int insertionIndex(T obj) {  
  26.     final TObjectHashingStrategy<T> hashing_strategy = _hashingStrategy;  
  27.   
  28.     final Object[] set = _set;  
  29.     final int length = set.length;  
  30.     final int hash = hashing_strategy.computeHashCode(obj) & 0x7fffffff;  
  31.     int index = hash % length;  
  32.     Object cur = set[index];  
  33.   
  34.     if (cur == FREE) {  
  35.         return index;       // empty, all done  
  36.     } else if (cur != REMOVED && hashing_strategy.equals((T) cur, obj)) {  
  37.         return -index -1;   // already stored  
  38.     } else {                // already FULL or REMOVED, must probe  
  39.         // compute the double hash  
  40.         final int probe = 1 + (hash % (length - 2));  
  41.   
  42.         // if the slot we landed on is FULL (but not removed), probe  
  43.         // until we find an empty slot, a REMOVED slot, or an element  
  44.         // equal to the one we are trying to insert.  
  45.         // finding an empty slot means that the value is not present  
  46.         // and that we should use that slot as the insertion point;  
  47.         // finding a REMOVED slot means that we need to keep searching,  
  48.         // however we want to remember the offset of that REMOVED slot  
  49.         // so we can reuse it in case a "new" insertion (i.e. not an update)  
  50.         // is possible.  
  51.         // finding a matching value means that we've found that our desired  
  52.         // key is already in the table  
  53.         if (cur != REMOVED) {  
  54.             // starting at the natural offset, probe until we find an  
  55.             // offset that isn't full.  
  56.             do {  
  57.                 index -= probe;  
  58.                 if (index < 0) {  
  59.                     index += length;  
  60.                 }  
  61.                 cur = set[index];  
  62.             } while (cur != FREE  
  63.                      && cur != REMOVED  
  64.                      && ! hashing_strategy.equals((T) cur, obj));  
  65.         }  
  66.   
  67.         // if the index we found was removed: continue probing until we  
  68.         // locate a free location or an element which equal()s the  
  69.         // one we have.  
  70.         if (cur == REMOVED) {  
  71.             int firstRemoved = index;  
  72.             while (cur != FREE  
  73.                    && (cur == REMOVED || ! hashing_strategy.equals((T) cur, obj))) {  
  74.                 index -= probe;  
  75.                 if (index < 0) {  
  76.                     index += length;  
  77.                 }  
  78.                 cur = set[index];  
  79.             }  
  80.             // NOTE: cur cannot == REMOVED in this block  
  81.             return (cur != FREE) ? -index -1 : firstRemoved;  
  82.         }  
  83.         // if it's full, the key is already stored  
  84.         // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)  
  85.         return (cur != FREE) ? -index -1 : index;  
  86.     }  
  87. }  

       从以上代码可以看出,THashMap使用Double hashing。用来计算增量的hash算法是final int probe = 1 + (hash % (length - 2));  如果insertionIndex()方法的返回值为正值,那么该值就是可用的slot位置;如果为负值,那么说明该key之前已经保存过,(-index-1)就是之前的slot位置。

 

      put()方法的流程如下, 根据key的hash值找到对应的set元素,判断是否存在hash冲突。

      如果不存在hash冲突,那么该set元素的可能状态如下:

  • FREE:意味着可以在该位置插入;
  • OCCUPIED,并且该元素的值等于put()方法的参数key:意味着该位置之前已经插入过相同key的数据,本次put操作需要对已有值进行替换;
  • 非以上两种情况:意味着存在hash冲突,需要进行probe;在probe的过程中不能轻易重用状态为REMOVED的set元素:如果在整个probe过程中没有发现与put()方法的参数key相等的set元素,那么才可以重用probe过程中遇到的第一个状态为REMOVED的set元素。

posted on 2010-11-17 14:03 flyonok 阅读(2365) 评论(0)  编辑 收藏 引用 所属分类: openssl


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理