Хэш таблицы

[akosh12345]

Уважаемые коллеги программисты. Мне нужна ваша помощь. Дело в том что я сейчас работаю над одним модулем. В нем я выделяю динамически память. И все эти куски храню в хэш таблице. Проводил тест. Создал хэш таблицу из 100 000 элементов(округлял до простого числа в большую сторону). И выделял память для 100 000 указателей.
К хеш функции отправлял адресс выделенной памяти. Как работала хэш функция: Я переводил адресс в usigned long и брал остаток от деления. Вот что получилось
0 - 35555
1 - 38328
2 - 19205
3 - 5855
4 - 1175
5 - 173
6 - 22
7 - 0
8 - 0
9 - 0
10 - 0
то есть у меня 35555 свободных ячеек в хеш таблице и так далее.
Согласитесь это очень не выгод. Больше 30% таблицы не используется. И эта цифра будет расти с увеличением хэш таблицы.

Провывал использовать CRC. Вот результат с теми же данными
0 - 37003
1 - 36971
2 - 18320
3 - 6115
4 - 1543
5 - 300
6 - 56
7 - 4
8 - 1
9 - 0
10 - 0

Провыбал использовать MD4 вот результат
0 - 36906
1 - 37025
2 - 18454
3 - 6055
4 - 1529
5 - 290
6 - 44
7 - 9
8 - 0
9 - 1
10 - 0
хотя здесь работают непосредственно с битами.


Помогите найти такую хэш функцию, которая хотя бы снизила количество неиспользуемых ячеек до 10%.
Или направить на путь!!!
Повторяюсь к хэш таблице приходят адресса памяти(к сведению они кратны 4)
заранее спасибо!!!

[Д_М]

Оптимальная загрузка хеш-таблицы (load factor) - 72%, у Вас 65%, что не так плохо. Если сделать больше - возрастает число коллизий и, как следствие, увеличивается время поиска.

Как подобрать правильную функцию - не знаю, коллизий у Вас многовато.

Альтернативный путь - реализация ассоциативного массива на двоичных деревьях (std::map напр.)