hash_table Struct Reference

Data structure for the hash table implementaion. More...

#include <util.h>

Collaboration diagram for hash_table:

[legend]

Data Fields
hash_struct_t *	arr
	The array containing the data.
int	cache
	A simple one item cache.
int	count
	Number of elements.
int	size
	Length of array.
int(*	hash_func )(void *key)
	Hash function.
int(*	compare_func )(void *key1, void *key2)
	Comparison function.

---

Detailed Description

Data structure for the hash table implementaion.

A hash table allows for retrieval and removal of any element in O(1), so long as a proper hash function is supplied.

The hash table is implemented using a single hash function and element storage directly in the array. When a collision occurs, the hashtable iterates until a zero element is found. When the table is 75% full, it will automatically reallocate itself. This reallocation takes O(n) time. The table is guaranteed to never be more than 75% full or less than 30% full (Unless the table is nearly empty). Its size is always a Mersenne number.

---

Field Documentation

int hash_table::cache

A simple one item cache.

This should always point to the index of the last item to be used

Referenced by hash_init(), hash_init2(), hash_realloc(), and hash_search().

---

The documentation for this struct was generated from the following file:

• util.h