I need to implement a hashtable array that works without initializing the array to zero at the beginning. Are there any tips on how to do this?

Question

So here is the actual question (this is for homework):

A hash table is a data structure that allows you to access and manipulate the date in constant time (O (1)). The hash table array must be initialized to zero during the creation of the hash table in order to identify empty cells. In most cases, the time penalty is huge, especially considering that most cameras will never be read. We ask you that you implement a hash table that bypasses this problem at the price of a heavier insert, but still in constant time. For this homework and to simplify your work, we assume that you cannot delete items in this hash table.

In the archive of this homework, you will find the hash table interface that you need to fill out. You can use the hashcode () function from java as a hash function. You will need to use the Vector data structure from Java to bypass initialization, and you must find how to do it yourself. You can only insert elements at the end of the vector so that the complexity is still O (1).

Here are some facts to consider:

• In a hash table containing integers, the table contains numeric values ​​(but they do not make any sense).

• On the stack, you cannot access elements above the highest element, but you know for sure that all values ​​are valid. In addition, you know the index of the highest element.

Use these facts to get around the hash table initialization. To resolve conflicts, the table must use linear sensing.

Also, here is the interface I need to implement for this homework:

public interface NoInitHashTable<E> { public void insert(E e); public boolean contains(E e); public void rehash(); public int nextPrime(int n); public boolean isPrime(int n); } 

I already implemented nextPrime and isPrime (I don't think they are different from a regular hash table). I need three others.

I thought about it a lot and discussed it with my teammate, but I really can't find anything. I only need to know the basic principle of its implementation, I can handle the encoding.

tl; dr I need to implement a hashtable array that works without initializing the array to zero at the beginning. Insertion should be performed at a constant time. I need to know only the basic principle of how to do this.

Answer 1

I think I saw this in a book as an exercise with an answer on the back, but I cannot remember which book or where. As a rule, this refers to the question of why we usually concentrate on the time taken by the program, and not on space - a program that works efficiently in time does not need huge amounts of space.

Here is some kind of pseudo code that checks the correctness of a cell in a hash table. I will leave the work of changing the data structures that it defines to make another cell in the hash table valid as the remaining exercise for the reader.

 // each cell here is for a cell at the same offset in the // hash table int numValidWhenFirstSetValid[SIZE]; int numValidSoFar = 0; // initialise only this // Only cells 0..numValidSoFar-1 here are valid. int validOffsetsInOrderSeen[SIZE]; boolean isValid(int offsetInArray) { int supposedWhenFirstValid = numValidWhenFirstSetValid[offsetInArray] if supposedWhenFirstValid >= numValidSoFar) { return false; } if supposedWhenFirstValid < 0) { return false; } if (validOffsetsInOrderSeen[supposedWhenFirstValid] != offsetInArray) { return false; } return true; } 

Edit is exercise 24 in section 2.2.6 of Knuth Vol 1. The answers provided say that 2.12 "Design and analysis of computer programs" by Aho, Hopcraft and Ullman. You can avoid any accusation of plagiarism in your answer by indicating the source of the question you asked :-)

Answer 2

Mark each item in the hash table with some color (1, 2, ...)

Fe Current Color:

 int curColor = 0; 

When you put an item in a hash table, associate the current color with it ( curColor )

If you need to search, filter elements that do not have the same color ( element.color == curColor )

If you need to clear hashTable just increase the current color ( curColor++ )