Java Collection Primitives
The Crater Dog Technologies™ Java Collection Framework contains a set of traditional style Java primitive collection classes that are used to implement the underlying functionality required by the Java Collection Framework classes. These primitive classes implement the normal interfaces defined in the java.util package. However, they have been optimized to provide better space-time tradeoffs than their counterparts in the java.util package. In some cases there are no counterparts that exist.
The standard java.util.ArrayList<E> collection class provides very good performance for random access usage. It has a couple limitations however:
- The underlying array has an arbitrary size and is scaled up by 50% as the number of elements in the list increases. This means that the resizing is not as efficient as it could be.
- Once the underlying array has scaled up, it never (automatically) scales back down again as elements are removed.
The craterdog.collections.primitives.DynamicArray<E> class addresses these issues without affecting the overall performance for random access usage. Instead of scaling linearly, the size is always a factor of two with a minimum size of 16. Each time the dynamic array needs more space it doubles in size. When the number of used slots in the dynamic array drops below 1/4th the size of the array, the size is halved.
The standard java.util.HashMap<K, V> collection class provides fairly good performance for random access usage. But it also has a few limitations:
- The hash function that it uses on the keys is not a true universal hash function and it also is not as fast as it could be.
- The number of buckets is never scaled back down once elements have been removed from the hash map.
- Each bucket is implemented as a linked list which is almost never faster than using a dynamic array.
The craterdog.collections.primitives.HashTable<K, V> class addresses these issues without affecting the overall performance for random access usage. As with the DynamicArray<E>, the HashTable<K, V> class has an initial (and minimum) size of 16 buckets and doubles the number of buckets each time it scales up. It also automatically scales down by halving the number of buckets when the elements drops below 1/4th the number of buckets. The biggest performance increase is gotten by using a true universal hash function that provides a very good random distribution of keys among the buckets no matter how bad the hash function of the key objects is. This hash function uses only shift operations making it an order of magnitude faster than mod based hash functions. See the description of the UniversalHashFunction class below for more details.
Most linked list implementations hide the actual links from the user's of the list. There are times, however, when it is useful to have direct access to the links themselves. This public class allows for this access and implements the insertion and deletion primitives for a doubly linked list.
A linked list is rarely, if ever, more efficient than a dynamic array based list and the java.util.LinkedList is no exception. It also tries to be more general than a linked list which causes its implementation to be suboptimal. The craterdog.collections.primitives.LinkedList<E> primitive collection class addresses these issues and provides a slight performance improvement over the java.util version. It also uses the craterdog.collections.primitives.Link<E> class which is useful in other contexts. But this the craterdog.collections.primitives.LinkedList<E> class is really just provided for completeness.
The standard java.util collection classes do not provide a primitive tree implementation. The java.util.TreeSet and java.util.TreeMap classes use a red-black tree implementation under-the-covers but it does not give the user the option of allowing duplicate elements. The craterdog.collections.primitives.RandomizedTree primitive class implements a generalized binary tree that is self balancing using a randomized approach defined here. It provides a slightly better performing binary tree than the one used by the standard java collections.