hash_table_internal.h File Reference

Internal HashTable API and utilities. More...

#include <stddef.h>
#include "hash_table.h"

Include dependency graph for hash_table_internal.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	hash_table

Functions
size_t	calc_load_threshold_count (size_t size)
	Precalculates the load threshold count.
HashTable *	hash_table_create_with_size (size_t size)
	Creates a new dynamically allocated HashTable object with a set size.
Entry **	create_buckets (size_t size)
	Creates a dynamically allocated bucket array with a set size.
void	clear_buckets (Entry **buckets, size_t size)
	Frees all entries inside a bucket array.
void	hash_table_resize (HashTable *table)
	Resizes the HashTable.
size_t	hash_function (int key, size_t table_size)
	Hash function using division method.
bool	is_prime (size_t n)
	Is prime function.
size_t	next_prime (size_t n)
	Finds the next prime number after n.

Variables
constexpr size_t	HT_INITIAL_SIZE = 53
	Initial hash table size, always a prime number.
constexpr double	HT_LOAD_THRESHOLD = 0.75
	The hash table grows if the count/size ratio exceeds this threshold.

Detailed Description

Internal HashTable API and utilities.

Function Documentation

calc_load_threshold_count()

size_t calc_load_threshold_count

(

size_t

size

)

Precalculates the load threshold count.

To reduce calculations, this method can be used to precalculate the threshold count. This way the threshold is only calculated if the table size changes.

Parameters

size	Table size

Returns

Threshold count

clear_buckets()

void clear_buckets	(	Entry **	buckets,
		size_t	size
	)

Frees all entries inside a bucket array.

Parameters

buckets	Bucket array
size	Size of the bucket array

create_buckets()

Entry ** create_buckets

(

size_t

size

)

Creates a dynamically allocated bucket array with a set size.

Parameters

size	Table size

Returns

Pointer to the bucket array

hash_function()

size_t hash_function	(	int	key,
		size_t	table_size
	)

Hash function using division method.

The hash is hash = key % table_size. The hash is always positive.

Parameters

key	Key to hash
table_size	Hash table size

Returns

Hashed key

hash_table_create_with_size()

HashTable * hash_table_create_with_size

(

size_t

size

)

Creates a new dynamically allocated HashTable object with a set size.

Parameters

size	Table size

Returns

Pointer to a dynamically allocated HashTable object

hash_table_resize()

void hash_table_resize

(

HashTable *

table

)

Resizes the HashTable.

Steps:

1. Calculate new bucket array size. It is the next prime after the double of the current size, found using next_prime()
2. Create new buckets and swap out the old one
3. Rehash all entries into new buckets using hash_table_insert()
4. Free old bucket

Parameters

table

Pointer to HashTable object

is_prime()

bool is_prime

(

size_t

n

)

Is prime function.

Using an optimized trial division method with the 6k ± 1 rule

next_prime()

size_t next_prime

(

size_t

n

)

Finds the next prime number after n.

Uses the is_prime() function.

Parameters

n	The prime is searched after n

Returns

Prime number