HashMap解决hash冲突的方法
HashMap 采用一种所谓的&Hash 算法&来决定每个元素的存储位置。当程序执行 map.put(String,Obect) 时，系统将调用String的 hashCode() 得到其 hashCode 值&&每个 Java 对象都有 hashCode() ，都可通过该获得它的 hashCode 值。得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值来决定该元素的存储位置。源码如下:
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry&K,V& e = table[i]; e != e = e.next) {
//判断当前确定的索引位置是否存在相同hashcode和相同key的元素，如果存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。
//如果存在相同的hashcode，那么他们确定的索引位置就相同，这时判断他们的key是否相同，如果不相同，这时就是产生了hash冲突。
//Hash冲突后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 链。
//系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止&&如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），
//那系统必须循环到最后才能找到该元素。
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.
return oldV
modCount++;
addEntry(hash, key, value, i);
当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。这也说明了前面的结论：我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可
Hashmap里面的bucket出现了单链表的形式，散列表要解决的一个问题就是散列值的冲突问题，通常是两种方法：链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式，链表是单向链表。形成单链表的核心代码如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry&K,V& e = table[bucketIndex];
table[bucketIndex] = new Entry&K,V&(hash, key, value, e);
if (size++ &= threshold)
resize(2 * table.length);
上面方法的代码很简单，但其中包含了一个设计：系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处&&如果 bucketIndex 索引处已经有了一个 Entry 对象，那新添加的 Entry 对象指向原有的 Entry 对象（产生一个 Entry 链），如果 bucketIndex 索引处没有 Entry 对象，也就是上面程序代码的 e 变量是 null，也就是新放入的 Entry 对象指向 null，也就是没有产生 Entry 链。
HashMap里面没有出现hash冲突时，没有形成单链表时，hashmap查找元素很快,get()方法能够直接定位到元素，但是出现单链表后，单个bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止&&如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那系统必须循环到最后才能找到该元素。
当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。
标签(Tag):
------分隔线----------------------------
------分隔线----------------------------bullet HashMap 内存紧密的哈希表
时间： 14:56:10
last modified time： 14:07:00
bullet 是一款开源物理引擎，它提供了碰撞检测、重力模拟等功能，很多3D游戏、3D设计软件（如3D Mark）使用它作为物理引擎。
作为物理引擎，对速度的要求是非常苛刻的；bullet项目之所以能够发展到今天，很大程度取决于它在速度上优异的表现。
bullet的源码就能看到很多源码级别的优化，本文将介绍的HashMap就是一个典例。
bullet项目首页：http://bulletphysics.org/
注：bullet很多函数定义了Debug版和Release版两个版本，本文仅以Release版为例。
btAlignedAllocator的接口定义
btAlignedAllocator是bullet定义的一个内存分配器接口，bullet的其他数据结构都使用它来管理内存。btAlignedAllocator的定义和STL的allocator（以下称std::allocator）类似：
///The btAlignedAllocator is a portable class for aligned memory allocations.
///Default implementations for unaligned and aligned allocations can be overridden by a custom allocator
using btAlignedAllocSetCustom and btAlignedAllocSetCustomAligned.
template & typename T , unsigned Alignment &
class btAlignedAllocator {
typedef btAlignedAllocator& T , Alignment & self_
//just going down a list:
btAlignedAllocator() {}
btAlignedAllocator( const self_type & ) {}
template & typename Other &
btAlignedAllocator( const btAlignedAllocator& Other , Alignment & & ) {}
typedef const T*
typedef const T&
typedef T*
typedef T&
( reference
ref ) const
{ return & }
const_pointer address
( const_reference
ref ) const
{ return & }
( size_type
, const_pointer *
hint = 0 ) {
return reinterpret_cast& pointer &(btAlignedAlloc( sizeof(value_type) * n , Alignment ));
construct ( pointer
ptr , const value_type &
) { new (ptr) value_type( value ); }
deallocate( pointer
btAlignedFree( reinterpret_cast& void * &( ptr ) );
{ ptr-&~value_type(); }
template & typename O & struct rebind {
typedef btAlignedAllocator& O , Alignment &
template & typename O &
self_type & operator=( const btAlignedAllocator& O , Alignment & & ) { return * }
friend bool operator==( const self_type & , const self_type & ) { }
与std::allocator类似，btAlignedAllocator的allocate和deallocate分别负责申请和释放内存空间，以release版编译的bulletbtAlignedAlloc/btAlignedFree分别为：
void* btAlignedAllocInternal (size_t size, int alignment);
void btAlignedFreeInternal (void* ptr);
#define btAlignedAlloc(size,alignment) btAlignedAllocInternal(size,alignment)
#define btAlignedFree(ptr) btAlignedFreeInternal(ptr)而btAlignedAllocInternal/btAlignedFreeInternal及其定制化的实现为：
static btAlignedAllocFunc *sAlignedAllocFunc = btAlignedAllocD
static btAlignedFreeFunc *sAlignedFreeFunc = btAlignedFreeD
void btAlignedAllocSetCustomAligned(btAlignedAllocFunc *allocFunc, btAlignedFreeFunc *freeFunc)
sAlignedAllocFunc = allocFunc ? allocFunc : btAlignedAllocD
sAlignedFreeFunc = freeFunc ? freeFunc : btAlignedFreeD
void* btAlignedAllocInternal (size_t size, int alignment)
gNumAlignedAllocs++; // 和gNumAlignedFree结合用来检查内存泄露
ptr = sAlignedAllocFunc(size, alignment);
// printf(&btAlignedAllocInternal %d, %x\n&,size,ptr);
void btAlignedFreeInternal (void* ptr)
gNumAlignedFree++; // 和gNumAlignedAllocs 结合用来检查内存泄露
// printf(&btAlignedFreeInternal %x\n&,ptr);
sAlignedFreeFunc(ptr);
如上，bullet内存分配的定制操作并不复杂，只需调用以下两个函数即可：
// The developer can let all Bullet memory allocations go through a custom memory allocator, using btAlignedAllocSetCustom
void btAlignedAllocSetCustom(btAllocFunc *allocFunc, btFreeFunc *freeFunc);
// If the developer has already an custom aligned allocator, then btAlignedAllocSetCustomAligned can be used.
// The default aligned allocator pre-allocates extra memory using the non-aligned allocator, and instruments it.
void btAlignedAllocSetCustomAligned(btAlignedAllocFunc *allocFunc, btAlignedFreeFunc *freeFunc);
无论是否定制自己的Alloc/Free（或AllignedAlloc/AlignedFree），bullet内的其他数据结构都使用btAlignedAllocator作为内存分配（回收）的接口。随后将会看到，btAlignedAllocator的定制化设计与std::allocator的不同，文末详细讨论。
btAlignedAllocator的内存对齐
btAlignedAllocator除了定制化与std::allocator不同外，还增加了内存对齐功能（从它的名字也能看得出来）。继续查看btAlignedAllocDefault/btAlignedFreeDefault的定义（btAlignedAllocator.{h|cpp}）可以看到：
#if defined (BT_HAS_ALIGNED_ALLOCATOR)
#include &malloc.h&
static void *btAlignedAllocDefault(size_t size, int alignment)
return _aligned_malloc(size, (size_t)alignment);
// gcc 提供了
static void btAlignedFreeDefault(void *ptr)
_aligned_free(ptr);
#elif defined(__CELLOS_LV2__)
#include &stdlib.h&
static inline void *btAlignedAllocDefault(size_t size, int alignment)
return memalign(alignment, size);
static inline void btAlignedFreeDefault(void *ptr)
free(ptr);
#else // 当前编译环境没有 对齐的（aligned）内存分配函数
static inline void *btAlignedAllocDefault(size_t size, int alignment)
real = (char *)sAllocFunc(size + sizeof(void *) + (alignment-1)); // 1. 多分配一点内存
if (real) {
ret = btAlignPointer(real + sizeof(void *),alignment);
// 2. 指针调整
*((void **)(ret)-1) = (void *)(real);
// 3. 登记实际地址
ret = (void *)(real);
return (ret);
static inline void btAlignedFreeDefault(void *ptr)
if (ptr) {
real = *((void **)(ptr)-1); // 取出实际内存块 地址
sFreeFunc(real);
bullet本身也实现了一个对齐的（aligned）内存分配函数，在系统没有对齐的内存分配函数的情况下，也能保证btAlignedAllocator::acllocate返回的地址是按特定字节对齐的。
下面就来分析btAlignedAllocDefault / btAlignedFreeDefault是如何实现aligned allocation / free的。sAllocFunc/sFreeFunc的定义及初始化：
static void *btAllocDefault(size_t size)
return malloc(size);
static void btFreeDefault(void *ptr)
free(ptr);
static btAllocFunc *sAllocFunc = btAllocD
static btFreeFunc *sFreeFunc = btFreeD
bullet同时提供了，AllocFunc/FreeFunc的定制化：
void btAlignedAllocSetCustom(btAllocFunc *allocFunc, btFreeFunc *freeFunc)
sAllocFunc = allocFunc ? allocFunc : btAllocD
sFreeFunc = freeFunc ? freeFunc : btFreeD
默认情况下sAllocFunc/sFreeFunc就是malloc/free，btAlignedAllocDefault中可能令人疑惑的是——为什么要多分配一点内存？后面的btAlignPointer有什么用？
再来看看bullet是如何实现指针对齐的（btScalar.h）：
///align a pointer to the provided alignment, upwards
template &typename T&T* btAlignPointer(T* unalignedPtr, size_t alignment)
struct btConvertPointerSizeT
btConvertPointerSizeT
const size_t bit_mask = ~(alignment - 1);
converter.ptr = unalignedP
converter.integer += alignment-1;
converter.integer &= bit_
return converter.
接下来分析btAlignPointer是如何调整指针的？
实际调用btAlignPointer时，使用的alignment都是2的指数，如btAlignedObjectArray使用的是16，下面就以16进行分析。
先假设unalignedPtr是alignment（16）的倍数，则converter.integer += alignment-1; 再 converter.integer &= bit_mask之后，unalignedPtr的值不变，还是alignment（16）的倍数。
再假设unalignedPtr不是alignment（16）的倍数，则converter.integer += alignment-1; 再converter.integer &= bit_mask之后，unalignedPtr的值将被到alignment（16）的倍数。
所以btAlignPointer能够将unalignedPtr对齐到alignment倍数。】
明白了btAlignPointer的作用，自然能够明白btAlignedAllocDefault中为什么多申请一点内存，申请的大小是size + sizeof(void *) + (alignment-1)：
如果sAllocFunc返回的地址已经按照alignment对齐，则sizeof(void*)和sizeof(alignment-1)及btAlignedAllocDefault的返回值关系如下图所示：
最后的alignment-1个字节的尾部无法使用，会被浪费，不过这很小（相对现在的内存条而言），管他呢！
如果sAllocFunc返回的地址没能按alignment对齐，则sizeof(void*)和sizeof(alignment-1)及btAlignedAllocDefault的返回值关系如下图所示：
PS: 顺便一提，为什么需要内存对齐呢？简单地说，按照机器字长倍数对齐的内存CPU访问的速度更快；具体来说，则要根据具体CPU和总线控制器的厂商文档来说的，那将会涉及很多具体的硬件平台细节，所以本文不会对该话题太多。
btAlignedObjectArray——bullet的动态数组
btAlignedObjectArray的作用与STL的vector类似，都是动态数组，btAlignedObjectArray的数据成员（data member）声明如下：
template &typename T&
class btAlignedObjectArray
btAlignedAllocator&T , 16& m_ // 没有data member，不会增加内存
//PCK: added this line
// ... 省略
btAlignedObjectArray同时封装了QuickSort，HeapSort，BinarySearch，LinearSearch函数，可用于排序、查找，btAlignedObjectArray的所有成员函数（member function）定义如下：
template &typename T&
//template &class T&
class btAlignedObjectArray
btAlignedAllocator&T , 16& m_
//PCK: added this line
#ifdef BT_ALLOW_ARRAY_COPY_OPERATOR
SIMD_FORCE_INLINE btAlignedObjectArray&T&& operator=(const btAlignedObjectArray&T& &other);
#else//BT_ALLOW_ARRAY_COPY_OPERATOR
SIMD_FORCE_INLINE btAlignedObjectArray&T&& operator=(const btAlignedObjectArray&T& &other);
#endif//BT_ALLOW_ARRAY_COPY_OPERATOR
protected:
SIMD_FORCE_INLINE int allocSize(int size);
SIMD_FORCE_INLINE void copy(int start,int end, T* dest)
SIMD_FORCE_INLINE void init();
SIMD_FORCE_INLINE void destroy(int first,int last);
SIMD_FORCE_INLINE void* allocate(int size);
SIMD_FORCE_INLINE void deallocate();
btAlignedObjectArray();
~btAlignedObjectArray();
///Generally it is best to avoid using the copy constructor of an btAlignedObjectArray,
and use a (const) reference to the array instead.
btAlignedObjectArray(const btAlignedObjectArray& otherArray);
/// return the number of elements in the array
SIMD_FORCE_INLINE int size()
SIMD_FORCE_INLINE const T& at(int n)
SIMD_FORCE_INLINE T& at(int n);
SIMD_FORCE_INLINE const T& operator[](int n)
SIMD_FORCE_INLINE T& operator[](int n);
///clear the array, deallocated memory. Generally it is better to use array.resize(0),
to reduce performance overhead of run-time memory (de)allocations.
SIMD_FORCE_INLINE void clear();
SIMD_FORCE_INLINE void pop_back();
///resize changes the number of elements in the array. If the new size is larger,
the new elements will be constructed using the optional second argument.
///when the new number of elements is smaller, the destructor will be called,
but memory will not be freed, to reduce performance overhead of run-time memory (de)allocations.
SIMD_FORCE_INLINE void resizeNoInitialize(int newsize);
SIMD_FORCE_INLINE void resize(int newsize, const T& fillData=T());
SIMD_FORCE_INLINE T&
expandNonInitializing( );
SIMD_FORCE_INLINE T&
expand( const T& fillValue=T());
SIMD_FORCE_INLINE void push_back(const T& _Val);
/// return the pre-allocated (reserved) elements, this is at least
as large as the total number of elements,see size() and reserve()
SIMD_FORCE_INLINE int capacity()
SIMD_FORCE_INLINE void reserve(int _Count);
class less
bool operator() ( const T& a, const T& b ) { return ( a & b ); }
template &typename L&
void quickSortInternal(const L& CompareFunc,int lo, int hi);
template &typename L&
void quickSort(const L& CompareFunc);
///heap sort from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Heap/
template &typename L&
void downHeap(T *pArr, int k, int n, const L& CompareFunc);
void swap(int index0,int index1);
template &typename L&
void heapSort(const L& CompareFunc);
///non-recursive binary search, assumes sorted array
int findBinarySearch(const T& key)
int findLinearSearch(const T& key)
void remove(const T& key);
//PCK: whole function
void initializeFromBuffer(void *buffer, int size, int capacity);
void copyFromArray(const btAlignedObjectArray& otherArray);
btAlignedObjectArray和std::vector类似，所以各成员函数的具体实现这里不再列出。
std::unordered_map的内存布局
btHashMap的内存布局与我们常见的HashMap的内存布局截然不同，为了和btHashMap的内存布局对比，这里先介绍一下std::unordered_map的内存布局。
GCC中std::unordered_map仅是对_Hahstable的简单包装，_Hashtable的数据成员定义如下：
__bucket_type*
_M_bucket_
__before_begin
_M_element_
_RehashPolicy
_M_rehash_其中，size_type为std::size_t的typedef；而_RehashPlolicy是具体的策略类，只有成员函数定义，没有数据成员（这是一种被称作Policy Based的设计范式，具体可参阅《Modern C++ Design》，中译本名为《C++设计新思维》，由侯捷先生翻译）。
继续跟踪_bucket_type，可以看到（_Hashtable）：
using __bucket_type = typename __hashtable_base::__bucket_和（__hashtable_base）：
using __node_base = __detail::_Hash_node_
using __bucket_type = __node_base*;
至此，才知道_M_buckets的类型为：_Hash_node_base**
继续追踪，可以看到_Hash_node_base的定义：
struct _Hash_node_base
Nodes, used to wrap elements stored in the hash table.
template parameter of class template _Hashtable controls whether
nodes also store a hash code. In some cases (e.g. strings) this
may be a performance win.
struct _Hash_node_base
_Hash_node_base* _M_
_Hash_node_base() : _M_nxt() { }
_Hash_node_base(_Hash_node_base* __next) : _M_nxt(__next) { }
从_Hashtable::_M_buckets（二维指针）和_Hash_node_base的_M_nxt的类型（指针），可以猜测Hashtable的内存布局——buckets数组存放hash值相同的node链表的头指针，每个bucket上挂着一个链表。
继续看__before_begin的类型（_Hashtable）：
using __before_begin = __detail::_Before_begin&_Node_allocator_type&;继续跟踪：
* This type is to combine a _Hash_node_base instance with an allocator
* instance through inheritance to benefit from EBO when possible.
template&typename _NodeAlloc&
struct _Before_begin : public _NodeAlloc
_Hash_node_base _M_
_Before_begin(const _Before_begin&) =
_Before_begin(_Before_begin&&) =
template&typename _Alloc&
_Before_begin(_Alloc&& __a)
: _NodeAlloc(std::forward&_Alloc&(__a))
};根据对STL双链表std::list的了解，可以猜测Berfore_begin的作用，很可能和双链表的“头部的多余的一个节点”类似，只是为了方便迭代器（iterator）迭代，通过_Hashtable::begin()可以得到验证：
begin() noexcept
{ return iterator(_M_begin()); }
__node_type*
_M_begin() const
{ return static_cast&__node_type*&(_M_before_begin()._M_nxt); }
const __node_base&
_M_before_begin() const
{ return _M_bbegin._M_ }
实际存放Value的node类型为下面两种的其中一种（按Hash_node_base的注释，Key为string时可能会用第一种，以提升性能）：
Specialization for nodes with caches, struct _Hash_node.
Base class is __detail::_Hash_node_base.
template&typename _Value&
struct _Hash_node&_Value, true& : _Hash_node_base
std::size_t
template&typename... _Args&
_Hash_node(_Args&&... __args)
: _M_v(std::forward&_Args&(__args)...), _M_hash_code() { }
_Hash_node*
_M_next() const { return static_cast&_Hash_node*&(_M_nxt); }
Specialization for nodes without caches, struct _Hash_node.
Base class is __detail::_Hash_node_base.
template&typename _Value&
struct _Hash_node&_Value, false& : _Hash_node_base
template&typename... _Args&
_Hash_node(_Args&&... __args)
: _M_v(std::forward&_Args&(__args)...) { }
_Hash_node*
_M_next() const { return static_cast&_Hash_node*&(_M_nxt); }
下面通过insert源码的追踪，证实我们对hashtable内存布局的猜想：
_Hashtable::insert：
template&typename _Pair, typename = _IFconsp&_Pair&&
__ireturn_type
insert(_Pair&& __v)
__hashtable& __h = this-&_M_conjure_hashtable();
return __h._M_emplace(__unique_keys(), std::forward&_Pair&(__v));
_Hashtable::_M_emplace（返回值类型写得太复杂，已删除）：
_M_emplace(std::true_type, _Args&&... __args)
// First build the node to get access to the hash code
__node_type* __node = _M_allocate_node(std::forward&_Args&(__args)...); // 申请链表节点 __args为 pair&Key, Value& 类型
const key_type& __k = this-&_M_extract()(__node-&_M_v); // 从节点中抽取 key
__hash_code __
__code = this-&_M_hash_code(__k);
__catch(...)
_M_deallocate_node(__node);
__throw_exception_
size_type __bkt = _M_bucket_index(__k, __code); // 寻找buckets上的对应hash code对应的index
if (__node_type* __p = _M_find_node(__bkt, __k, __code)) // 在bucket所指链表上找到实际节点
// There is already an equivalent node, no insertion
_M_deallocate_node(__node);
return std::make_pair(iterator(__p), false);
// Insert the node
return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
_Hashtable::_M_find_node：
__node_type*
_M_find_node(size_type __bkt, const key_type& __key,
__hash_code __c) const
__node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
if (__before_n)
return static_cast&__node_type*&(__before_n-&_M_nxt);
_Hashtable::_M_find_before_node（返回值类型写得太复杂，已删除）：
_M_find_before_node(size_type __n, const key_type& __k,
__hash_code __code) const
__node_base* __prev_p = _M_buckets[__n]; // 取出头指针
if (!__prev_p)
__node_type* __p = static_cast&__node_type*&(__prev_p-&_M_nxt);
for (;; __p = __p-&_M_next()) // 遍历链表
if (this-&_M_equals(__k, __code, __p)) // key匹配？
return __prev_p;
if (!__p-&_M_nxt || _M_bucket_index(__p-&_M_next()) != __n)
__prev_p = __p;
看到_Hashtable::_M_find_before_node的代码，就验证了此前我们对于Hashtable内存布局的猜想：这和SGI hash_map的实现体hashtable的内存布局相同（详情可参考《STL源码剖析》，侯捷先生著）。
（PS：追踪起来并不轻松，可以借助Eclipse等集成开发环境进行）
例如，std::unordered_map&int, int*&背后的Hashtable的一种可能的内存布局如下：
std::unordered_map的内存布局是大多数&数据结构&、&算法&类教材给出的“标准做法”，也是比较常见的实现方法。
btHashMap的内存布局，与“标准做法”截然不同，如下可见btHashMap的数据成员（data member）定义：
template &class Key, class Value&
class btHashMap
protected:
btAlignedObjectArray&int&
btAlignedObjectArray&int&
btAlignedObjectArray&Value&
btAlignedObjectArray&Key&
// ... 省略
};可以看到，btHashMap的将buckets和key, value全放在一起，它的内存布局可能如下：
接下来通过分析btHashMap的几个方法的实现，来确定btHashMap三个btAlignedObjectArray的具体作用。
btHashMap::findIndex
下面来看看btHashMap::findIndex的实现：
int findIndex(const Key& key) const
unsigned int hash = key.getHash() & (m_valueArray.capacity()-1); // 依赖 Key::getHash()
if (hash &= (unsigned int)m_hashTable.size())
return BT_HASH_NULL;
int index = m_hashTable[hash]; // index相当于unordered_map的buckets[hash]的链表头指针
while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false) // 遍历链表，直到匹配，依赖 Key::equals(Key)
index = m_next[index];
}btHashMap::findIndex用到了m_hashTable，它的作用类似于unordered_map的buckets数组；m_next则类似于unordered_map链表节点的next指针。
btHashMap::insert
接下来看看btHashMap::insert：
void insert(const Key& key, const Value& value) {
int hash = key.getHash() & (m_valueArray.capacity()-1);
//replace value if the key is already there
int index = findIndex(key); // 找到了&Key, Value&节点
if (index != BT_HASH_NULL)
m_valueArray[index]= // 找到了，更行value
int count = m_valueArray.size(); // 当前已填充数目
int oldCapacity = m_valueArray.capacity();
m_valueArray.push_back(value); // value压入m_valueArray的尾部，capacity可能增长
m_keyArray.push_back(key);
// key压入m_keyArray的尾部
int newCapacity = m_valueArray.capacity();
if (oldCapacity & newCapacity)
growTables(key); // 如果增长，调整其余两个数组的大小，并调整头指针所在位置
//hash with new capacity
hash = key.getHash() & (m_valueArray.capacity()-1);
m_next[count] = m_hashTable[hash]; // 连同下一行，将新节点插入 m_hashTable[hash]链表头部
m_hashTable[hash] =
这里验证了我们对于m_hashTables和m_next作用的断言。
btHashMap::remove
btHashMap与普通Hash表的区别在于，它可能要自己管理节点内存；比如，中间节点remove掉之后，如何保证下次insert能够复用节点内存？通过btHashMap::remove可以知道bullet是如何实现的：
void remove(const Key& key) {
int hash = key.getHash() & (m_valueArray.capacity()-1);
int pairIndex = findIndex(key); // 找到&Key, Value&的 index
if (pairIndex ==BT_HASH_NULL)
// Remove the pair from the hash table.
int index = m_hashTable[hash];
// 取出头指针
btAssert(index != BT_HASH_NULL);
int previous = BT_HASH_NULL;
while (index != pairIndex)
// 找index的
previous =
index = m_next[index];
if (previous != BT_HASH_NULL)
// 将当前节点从链表上删除
btAssert(m_next[previous] == pairIndex);
m_next[previous] = m_next[pairIndex];
// 当前节点位于链表中间
m_hashTable[hash] = m_next[pairIndex]; // 当前节点是链表第一个节点
// We now move the last pair into spot of the
// pair being removed. We need to fix the hash
// table indices to support the move.
int lastPairIndex = m_valueArray.size() - 1;
// If the removed pair is the last pair, we are done.
if (lastPairIndex == pairIndex) // 如果&Key, Value&已经是array的最后一个元素，则直接调整它的size（仅为游标，capacity才是持有的内存单位个数）
m_valueArray.pop_back();
m_keyArray.pop_back();
// Remove the last pair from the hash table. 将最后一个&Key, Value&对从array除
int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity()-1);
index = m_hashTable[lastHash];
btAssert(index != BT_HASH_NULL);
previous = BT_HASH_NULL;
while (index != lastPairIndex)
previous =
index = m_next[index];
if (previous != BT_HASH_NULL)
btAssert(m_next[previous] == lastPairIndex);
m_next[previous] = m_next[lastPairIndex];
m_hashTable[lastHash] = m_next[lastPairIndex];
// Copy the last pair into the remove pair's spot.
将最后一个&Key, Value&拷贝到移除pair的处
m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
m_keyArray[pairIndex] = m_keyArray[lastPairIndex];
// Insert the last pair into the hash table , 将移除节点插入到m_hashTable[lastHash]链表的头部
m_next[pairIndex] = m_hashTable[lastHash];
m_hashTable[lastHash] = pairI
m_valueArray.pop_back();
m_keyArray.pop_back();
内存紧密（连续）的好处
btHashMap的这种设计，能够保证整个Hash表内存的紧密（连续）性；而这种连续性的好处主要在于：
第一，能与数组（指针）式API兼容，比如很多OpenGL API。因为存在btHashMap内的Value和Key在内存上都是连续的，所以这一点很好理解；
第二，保证了cache命中率（表元素较）。由于普通链表的节点内存是在每次需要时才申请的，所以基本上不会连续，通常不在相同内存页。所以，即便是短时间内多次访问链表节点，也可能由于节点内存分散造成不能将所有节点放入cache，从而导致访问速度的下降；而btHashMap的节点内存始终连续，因而保证较高的cache命中率，能带来一定程度的提升性能。
btAlignedAllocator点评
btAlignedAllocator定制化接口与std::allocator完全不同。std::allocator的思路是：首先实现allocator，然后将allocator作为模板参数写入具体数据结构上，如vector&int, allocator&int& &；
这种方法虽然可以实现“定制化”，但存在着一定的问题：
第一，由于所有标准库的allcoator用的都是std::allocator，如果你使用了另外一种allocator，程序中就可能存在不止一种类型的内存管理方法一起工作的局面；特别是当标准库使用的是SGI 当年实现的“程序退出时才所有内存的”allocator（具体可参阅《STL源码剖析》）时，内存争用是不可避免的。
第二，这种设计无形中增加了编码和调试的复杂性，相信调试过gcc STL代码的人深有体会。
而btAlignedAllocator则完全不存在这样的问题：
第一，它的allocate/deallocate行为通过全局的函数指针代理实现，不可能存在同时有两个以上的类型的底层管理内存的方法。
第二，这种相对简单，编码调试的复杂性自然降低了。
本人，STL有点过度设计了，虽然Policy Based的设计能够带来灵活性，但代码的可读性下降了很多（或许开发glibc++的那群人没打算让别人看他们的代码?）。
文中提到了两本书：
《Modern C++ Design》（中译本名为《C++设计新思维》，侯捷先生译），细致描述了Policy Based Design。
《STL源码剖析》（侯捷先生著），该书详细剖析了SGI hashtable的实现。
本文所讨论的源码：
bullet 2.81，源码目录：
gcc 4.6.1（MinGW）
欢迎评论或email（）交流观点，转载注明出处，勿做商用。
.net集合类的研究-哈希表（一）--Hashtable,Dictionary
.net集合类的研究--哈希表(二)--HashSet
$T.total > 0 && $T.page <= $T.pageNum}
{#foreach $T.data as r}
{$T.r.formt_tm}{#if $T.r.nickname}{#else}匿名{#/if}
{$T.r.content}
{#if $T.page > 1 && $T.pageNum > 1)
$T.s_num > 2}
{#for index = $T.s_num to $T.e_num}
$T.pageNum > $T.pageNavSize+ 2 && $T.s_num != $T.pageNum - $T.pageNavSize}
{#if $T.pageNum > 1}
{#if $T.pageNum != $T.page && $T.pageNum > 1}
<a href="javascript:void(0);" page="{$T.page 下一页
您的回应...
也许你感兴趣
(C)2012 本站提供的内容来源于广大网络用户，我们不保证内容的正确性。如果转载了您的内容，希望删除的请联系我们！