I have to use a hash table to store my collision data, and the btHashMap, wich is also cluded in the library seems the way to go, because of the SIMD code optimizations.
Inspecting the source code I've found that searching for an element in a btHashMap depends on the number of stored elements, so it is not really O(1) but O(n).
Code: Select all
Value* find(const Key& key)
{
int index = findIndex(key);
if (index == BT_HASH_NULL)
{
return NULL;
}
return &m_valueArray[index];
}
int findIndex(const Key& key) const
{
unsigned int hash = key.getHash() & (m_valueArray.capacity()-1);
if (hash >= (unsigned int)m_hashTable.size())
{
return BT_HASH_NULL;
}
int index = m_hashTable[hash];
while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false)
{
index = m_next[index];
}
return index;
}