hash_table.h File Reference

Open-addressing string→int hash table with linear probing. More...

#include <stdbool.h>
#include <stddef.h>

Go to the source code of this file.

Typedefs
typedef struct hash_table	hash_table_t

Functions
size_t	ht_capacity (const hash_table_t *ht)
bool	ht_contains (const hash_table_t *ht, const char *key)
hash_table_t *	ht_create (void)
void	ht_destroy (hash_table_t *ht)
bool	ht_get (const hash_table_t *ht, const char *key, int *out)
bool	ht_remove (hash_table_t *ht, const char *key)
bool	ht_set (hash_table_t *ht, const char *key, int value)
size_t	ht_size (const hash_table_t *ht)

Detailed Description

Open-addressing string→int hash table with linear probing.

Open addressing was chosen over separate chaining for cache locality and zero per-entry malloc churn. Linear probing in particular keeps the math simple; the load factor is capped at 0.75 with auto-resize.

Hash function: djb2 (k=33) — fast, good enough for non-adversarial data.

Operation	Avg	Worst
get	O(1)	O(n)
set	O(1)	O(n)
remove	O(1)	O(n)
resize (rehash)	O(n)	(amortized into set)

Definition in file hash_table.h.

Typedef Documentation

hash_table_t

typedef struct hash_table hash_table_t

Definition at line 25 of file hash_table.h.

Function Documentation

ht_capacity()

size_t ht_capacity

(

const hash_table_t *

ht

)

Definition at line 123 of file hash_table.c.

References hash_table::capacity.

Referenced by main().

ht_contains()

bool ht_contains	(	const hash_table_t *	ht,
		const char *	key
	)

Definition at line 118 of file hash_table.c.

References ht_get().

ht_create()

hash_table_t * ht_create

(

void

)

Definition at line 40 of file hash_table.c.

References hash_table::capacity, HT_INITIAL_CAPACITY, hash_table::size, and hash_table::slots.

Referenced by main().

ht_destroy()

void ht_destroy

(

hash_table_t *

ht

)

Definition at line 50 of file hash_table.c.

References hash_table::capacity, ht_slot_t::key, SLOT_OCCUPIED, hash_table::slots, and ht_slot_t::state.

Referenced by main().

ht_get()

bool ht_get	(	const hash_table_t *	ht,
		const char *	key,
		int *	out
	)

Writes *out and returns true if found, otherwise false.

Definition at line 99 of file hash_table.c.

References hash_table::capacity, probe(), SLOT_OCCUPIED, hash_table::slots, ht_slot_t::state, and ht_slot_t::value.

Referenced by ht_contains(), and main().

ht_remove()

bool ht_remove	(	hash_table_t *	ht,
		const char *	key
	)

Definition at line 107 of file hash_table.c.

References hash_table::capacity, ht_slot_t::key, probe(), hash_table::size, SLOT_OCCUPIED, SLOT_TOMBSTONE, hash_table::slots, and ht_slot_t::state.

Referenced by main().

ht_set()

bool ht_set	(	hash_table_t *	ht,
		const char *	key,
		int	value
	)

Inserts or updates key → value. Returns false on allocation failure.

Definition at line 77 of file hash_table.c.

References hash_table::capacity, HT_MAX_LOAD, ht_resize(), ht_slot_t::key, probe(), hash_table::size, SLOT_OCCUPIED, hash_table::slots, ht_slot_t::state, and ht_slot_t::value.

Referenced by main().

ht_size()

size_t ht_size

(

const hash_table_t *

ht

)

Definition at line 122 of file hash_table.c.

References hash_table::size.

Referenced by main().