A hash table is a common data structure in which an unordered set of elements is stored. It is possible to tell whether an element is in the set in O(1) time, instead of O(n) for an array or O(log n) for a tree.

The simplest hash tables are arrays connected to a linked list. In this TI-BASIC implementation, we can make the linked list and the array in a complex list L3 and a real list L1, respectively. Our elements will be real numbers, and as a TI-BASIC list is limited to 999 elements, we can only store a few hundred elements. On monochrome/CSE calculators, there is also a memory restriction, as a 999-element complex list takes 18k out of the total 24k of user memory.

First, we need a hash function that assigns a number to one of say 257 buckets, from 1 to 257. Here's one possible function, just taking X mod 257.


Code:


In the following code, L1(B) is the pointer to L3 for bucket B. L3(A) has data in the real part, and a pointer to the next element in the complex part. Null is zero.

We can add an element X thusly:

Code:


This should take 10 or 20 ms on average when the hash table isn't too full.

We can also check if an element is in the set (untested):


Code:

One of the key problems to solve with hash tables is collisions, because of course the ideal hash table where every key hashes to a unique slot is an impossibility. Current techniques to resolve this include the linked list you mentioned, where a slot that contains multiple elements becomes a linked list, chaining, where multiple hash functions are defined, and the slot specified by the second, third, ..., nth hash function is tested if the previous n-1th are full, binning, and of course rehashing. What implementation are you going to approach? You mentioned 256 buckets there.

For robust performance, you'll want to look into universal hash functions. The simplest implementation involves basic arithmetic modulo a prime.

Only if your set of keys is dynamic!