btHashMap performance in collision filter callback

[rraallvv]

The built-in collision filter groups and masks are not enough to store the information needed by my collision filter callback.

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;
	}

Although the table will be storing no more than 10 elements, would it be a performance hit to use btHashMap in that way?

[xexuxjy]

as it's a hashmap it will in most cases be O(1) depending on your hashing function... if you look at the code it only searches linearly if it doesn't get a match on first hash lookup...

[rraallvv]

as it's a hashmap it will in most cases be O(1) depending on your hashing function... if you look at the code it only searches linearly if it doesn't get a match on first hash lookup...

I'm using the Fowler / Noll / Vo (FNV) hash harcoded in the btHashString class.

I'll try with the btHashTable to see how well run the simulation.