Note: This website is archived. For up-to-date information about D projects and development, please visit

KeyIndex and KeyValueIndex templates.

Indexing and value association facility that can be applied to an existing array in place.

The idea and the code were adapted from the "Ultimate++" sources Index.h, Index.hpp Index.cpp, and reworked in D idiom, with a reduction in the number functions by inlining, and reducing the code to the basic concepts necessary to support a KeyIndex, and KeyValueIndex templates.

The Ultimate++ has an overall BSD license, but this as implementation is no longer in C++, and the underlying ideas are simple enough, nor have I been easily able to find other similar implementations, so its "open source".

Insertion into a full array always results in incrementing the length of the managed hash_, links_ arrays. These increases avoid frequent reallocations by monitoring the array capacity.

The insertion index is always shared between hash_, links_ and additional keys_ or keys_ plus values_. If a free link exists, then the index of that is used. The length property indicates the number of occupied slots. If no freelinks then the arrays are compact, without holes. Empty slots are marked by setting the Hibit in the hash array entry, and adding the associated index link record to the freelinks. Associated keys and values remain untouched until potentially the next insertion, or can be managed by a call back OnRemove delegate.

Links are chained from hash collisions and duplicates of course.

The KeyIndex template, and the indexArray method can be used to index an existing array in place.

Performance gets slower than the builtin druntime hash map implementation. On reaching larger array sizes of 1_000_000,it compares to be about 25% slower. The builtin AA does allocate memory nodes incrementally which only need to be relinked when the main hash table grows, whereas this implementation has to reallocate all of the arrays each time array capacity is exceeded. Excess reallocation can be avoided by preset call to capacity, but its still a little slower, but useable at larger array sizes.

Performance of KeyIndex will degrade if lots of duplicate keys, or bad hash distribution. The HashMap implementation maintains unique keys with findPut.

With separate arrays and use of integers instead of pointers to aggregated nodes, it may be a little more immune to garbage collection issues that druntime AA can get.

But not entirely immune however, as "memory allocation failure" exception did occur during development testing, with large arrays string keys, when a bug meant that key and value arrays where being incremented by length, instead of capacity managed.

The source code is found in hash/arrayindex.d