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:
`1+remainder(int(X),257`

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:
```1+dim(L3->I X->L3(I       //imaginary part (pointer) already zero 1+remainder(int(X),257    //bucket number If L1(Ans Then L1(Ans While imag(L3(Ans imag(L3(Ans End L3(Ans)+[i]I->L3(Ans Else I->L1(Ans End```

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:
```1+remainder(int(N),257 If L1(Ans Then    L3(L1(Ans  //initial element and pointer    While N!=real(Ans) and imag(Ans  //while no match and not null       imag(Ans->I%    //next pointer       L3(I%    End    N=real(Ans    Else    0 End```
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.
KermMartian wrote:
because of course the ideal hash table where every key hashes to a unique slot is an impossibility.

Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

»
» All times are UTC - 5 Hours

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum