Dalvik vm Hash interface

Dalvik VM 哈希表 之 接口篇

几乎在所有的高级语言中都有哈希表（hashmap）的支持。它已经成为很多语言内建的数据类型。但是C语言创建较早，没有内建的哈希表类型的支持。我们只能通过库的实现来支持。如果仅仅想使用哈希表又不想引入整个库，我们可以简单的实现哈希表。Dalvik就是这么做的。

dalvik哈希表的代码在 dalvik/vm/hash.c  dalvik/vm/hash.cpp 里，它为dalvik其他的模块提供了创建，使用，销毁哈希表的常用方法。 下面我们从 接口，使用和实现三个角度来看看 dalvik哈希表：

接口

/*
* Create and initialize a HashTable structure, using "initialSize" as
* a basis for the initial capacity of the table. (The actual initial
* table size may be adjusted upward.) If you know exactly how many
* elements the table will hold, pass the result from dvmHashSize() in.)
*
* Returns "false" if unable to allocate the table.
*/
HashTable* dvmHashTableCreate(size_t initialSize, HashFreeFunc freeFunc)
           

创建一个哈希表，并制定初始的大小和回调函数用来哈希表释放。 初始大小用于开始无法精确得知最终该哈希表大小的情况，如果随着哈希表单元（Entry）增加，原始的容量不够，该哈希表是可以动态增加容量的。释放函数用来释放哈希表单元所占据的资源。

/*
* Compute the capacity needed for a table to hold "size" elements. Use
* this when you know ahead of time how many elements the table will hold.
* Pass this value into dvmHashTableCreate() to ensure that you can add
* all elements without needing to reallocate the table.
*/
size_t dvmHashSize(size_t size)
           

如果我们预先知道要使用的哈希表的单元的数量，我们可以使用这个方法来计算容纳这么多数量单元的哈希表所需要的大小。因而可以在创建哈希表是指定精确的初始值大小。这样子可以减少动态增加容量所带来的额外开销。但是多数情况下我们创建哈希表之前难以获知哈希表的精确大小，所以该方法在dalvik实现里很少使用到。

/*
* Clear out a hash table, freeing the contents of any used entries.
*/
void dvmHashTableClear(HashTable* pHashTable)
           

清除哈希表。用于调用dvmHashTableCreate传入的freeFunc释放掉每个哈希单元所占据的资源，并将哈希表单元数量置零。但是该方法并不释放改哈希表本身。

/*
* Free a hash table. Performs a "clear" first.
*/
void dvmHashTableFree(HashTable* pHashTable);
           

释放哈希表。在调用dvmHashTableClear清除哈希表后，释放改哈希表本身，这样该哈希表所占用的所有内存都将释放。

/*
* Exclusive access. Important when adding items to a table, or when
* doing any operations on a table that could be added to by another thread.
*/
INLINE void dvmHashTableLock(HashTable* pHashTable) {
dvmLockMutex(&pHashTable->lock);
}
INLINE void dvmHashTableUnlock(HashTable* pHashTable) {
dvmUnlockMutex(&pHashTable->lock);
}
           

加锁和解锁哈希表。用于排他性的访问该哈希表。如果我们需要同步方法改哈希表，这两个操作是必须的。

/*
* Get #of entries in hash table.
*/
INLINE int dvmHashTableNumEntries(HashTable* pHashTable) {
return pHashTable->numEntries;
}
           

获得哈希表单元数量。

/*
* Get total size of hash table (for memory usage calculations).
*/
INLINE int dvmHashTableMemUsage(HashTable* pHashTable) {
return sizeof(HashTable) + pHashTable->tableSize * sizeof(HashEntry);
}
           

获得该哈希表所占据的内存总量。

/*
* Look up an entry in the table, possibly adding it if it's not there.
*
* If "item" is not found, and "doAdd" is false, NULL is returned.
* Otherwise, a pointer to the found or added item is returned. (You can
* tell the difference by seeing if return value == item.)
*
* An "add" operation may cause the entire table to be reallocated. Don't
* forget to lock the table before calling this.
*/
void* dvmHashTableLookup(HashTable* pHashTable, u4 itemHash, void* item,
HashCompareFunc cmpFunc, bool doAdd);
           

哈希表查找。用于在指定哈希表中查找某个单元。如果指定doAdd为true，那么在没有找到该单元后将该单元加入该哈希表。

/*
* Remove an item from the hash table, given its "data" pointer. Does not
* invoke the "free" function; just detaches it from the table.
*/
bool dvmHashTableRemove(HashTable* pHashTable, u4 hash, void* item);
           

在哈希表中标记某单元已移除。该函数并不调用free函数清理改单元所占据的内存，而是简单的标记该单元不再使用。

/*
* Execute "func" on every entry in the hash table.
*
* If "func" returns a nonzero value, terminate early and return the value.
*/
int dvmHashForeach(HashTable* pHashTable, HashForeachFunc func, void* arg);
           

遍历哈希表，并为每个单元调用指定的函数，并传入参数。如果某个单元调用的函数返回非零值，那么就终止遍历，并返回改值。

/*
* Execute "func" on every entry in the hash table.
*
* If "func" returns 1 detach the entry from the hash table. Does not invoke
* the "free" function.
*
* Returning values other than 0 or 1 from "func" will abort the routine.
*/
int dvmHashForeachRemove(HashTable* pHashTable, HashForeachRemoveFunc func);
           

遍历哈希表，为每个表单元调用函数func。如果该函数返回1，那么就将该单元标记为不可用。如果遍历过程中，某个函数返回值既不是0也不是1，那么遍历将提前结束。

/*
* An alternative to dvmHashForeach(), using an iterator.
*
* Use like this:
* HashIter iter;
* for (dvmHashIterBegin(hashTable, &iter); !dvmHashIterDone(&iter);
* dvmHashIterNext(&iter))
* {
* MyData* data = (MyData*)dvmHashIterData(&iter);
* }
*/
struct HashIter {
void* data;
HashTable* pHashTable;
int idx;
};
INLINE void dvmHashIterNext(HashIter* pIter)
INLINE void dvmHashIterBegin(HashTable* pHashTable, HashIter* pIter)
INLINE bool dvmHashIterDone(HashIter* pIter)
INLINE void* dvmHashIterData(HashIter* pIter)
           

提供一种是用遍历器方式遍历哈希表。