Inherited from NULL

Inherited by NULL

Friend class HashIterator,HashCleaner,

Description

哈希（Hash）也称散列，哈希表是一种与数组、链表等不同的数据结构，与他们需要不断的遍历比较来查找的办法，哈希表设计了一个映射关系f(key)= address，根据key来计算存储地址address，这样可以1次查找，f既是存储数据过程中用来指引数据存储到什么位置的函数，也是将来查找这个位置的算法，叫做哈希算法。 XHash 是XT针对工程计算中大量用到的拥有整数ID的数据对象深入优化之后开发出的哈希工具类，它创造性的丢弃了传统的链表结构而用数组结构来储存拥有同一个哈希值的对象，而该数组也随着对象的多少可动态调整，与XT的内存池MemPool类使用，一方面可以避免内存的水平化，另一方面也极大的提高了数据添加、修改、查找与删除的性能。
存储管理数据地址，使用取模的Hash运算快速定位数据地址。XHash采用开散列法处理哈希碰撞（不同关键字通过相同哈希哈数计算出相同的哈希地址，映射到了相同位置，该种现象称为哈希冲突或哈希碰撞），该方法又叫哈希桶，首先对关键码集合用散列函数计算散列地址，发生哈希冲突的具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点地址存储在哈希表中。获取数据的时候只需要Hash运算后拿到下标，然后拿到哈希桶中比对是否为获取的数据即可，由于Hash冲突并不是每次都会发生，其次因为会不断的进行动态扩容所以碰撞几率会减少，所以冲突的链表并不会像开放寻址法的数组那样长。开散列中每个桶中放的都是发生哈希冲突的元素。 Hash由基本索引表（Base Index Table，以下简称BIT）和一个用于分配Hash节点的内存池组成，基本索引表的长度表征了Hash的大小。在XHash中哈希桶是一个对象指针数组（XItemPtrArray<XItem, 2>），它是一个初始容量为2的对象指针数组，该数组可根据冲突的个数动态调整容量，由于该数组所占空间较小，它从XHash的内存池空间中分配。由Hash定位的数据需要提供一个函数（IdGetter）以获取唯一标识它的整型数，将此整型数对基本索引表的长度取模，得到的余数就是该数据在Hash中的索引。原则上该数据的地址存在基本索引表余数对应的位置上，如果有两个数据拥有相同的索引，则将该数据添加到对应哈希桶中。
为了最大提高哈希表的索引速度并更加有效的利用内存，哈希表的平均冲突次数为2或3（即对象的个数与基本索引表的长度的比值），XHash提供了函数用于指定该指标，当对象的个数与基本索引表的长度的比值超过该值时，自动计算新的最优索引长度然后重建对象索引。重建对象索引相对耗时，一般在已经知道对象规模的情况下，通过预先指定哈希表的索引长度可避免重建对象索引的过程。

为了减小数据冲突，基本索引表的大小应选择适合的质数。 为了避免某些情况下嵌套的遍历过程所导致的冲突，对Hash数据的遍历引入到HashIterator完成。

Members

• XItemPtrArray<XItem, 2> * m_pHashLinkTable
• ulong m_ulCount
• ulong m_ulModNumber
• MemPool * m_pHashPool
• bool m_bSelfPool

Public interface

• THash(ulong hashSize,MemPool * pMemPool = 0)
• bool insert(T *pData)
• void remove(ulong id)
• void clear()
• void resize(ulong newSize)
• T * getData(ulong id)
• T * operator [] (ulong id)
• ulong getCount()
• ulong getSize()
• void setIterator(Iterator * pIter)

XItemPtrArray<XItem, 2>* m_pHashLinkTable

Hash基本索引表，Hash的节点为XItemPtrArray<XItem, 2>类型

ulong m_ulCount

节点的总个数

ulong m_ulModNumber

用于取模运算的模数，也是节点基本表的大小，一般为质数

MemPool * m_pHashPool

当添加一个引起索引冲突的节点时，该节点的空间由该内存池分配

bool m_bSelfPool

内存池来源于外部指定，则为false，若由自己创建，则为true

THash(ulong hashSize,MemPool * pMemPool = 0)

• function: 构造Hash对象
• parameters:
  1. [i]ulong hashSize: 期望的hash的节点规模，取值范围下限大于0，上限取决于内存空间大小。hashSize决定了m_ulModNumber的值（比m_ulHashSize/2大的质数）
  2. [i]MemPool * pMemPool = 0： 从外部指定用于分配节点空间的内存池，默认为不从外部指定，即为NULL
• return value: 无

bool insert(T *pData)

• function: 将数据pData插入到Hash中
• parameters:
  1. [i]T *pData: 插入的数据
• return value: 若插入成功则返回true，若插入失败或者数据已在hash中返回false

void remove(ulong id)

• function: 将数字标识为id的数据从Hash中删除
• parameters:
  1. [i]ulong id: 需要删除的数据的数字标识
• return value: 无

void clear()

• function: 重置基本索引表为空白状态，释放由内存池分配的节点空间，如果内存池是自行创建，重置内存池
• parameters: NULL
• return value: 无

void resize(ulong newSize)

• function:
• parameters: 重新设置Hash的大小，并将原Hash的数据添加到新的Hash中
  1. [i]ulong newSize: hash的新的容量
• return value: 无

T * getData(ulong id)

• function: 获取数字标识为id的数据地址
• parameters:
  1. [i]ulong id: 待获取数据的id
• return value: 若Hash中有匹配的数据，则返回数据的地址，否则返回NULL

T * operator [] (ulong id)

• function: 获取数字标识为id的数据地址
• parameters:
  1. [i]ulong id: 待获取数据的id
• return value: 若Hash中有匹配的数据，则返回数据的地址，否则返回NULL

ulong getCount()

• function: 获取节点总数
• parameters: NULL
• return value: 节点总数

ulong getSize()

• function: 获取Hash表的大小
• parameters: NULL
• return value: Hash基本索引表的长度

void setIterator(Iterator * pIter)

• function: 绑定遍历迭代器
• parameters:
  1. [i]Iterator * pIter：遍历迭代器的指针，该指针必须有效
• return value: 无