Specifications: Hash Dictionary – an array named hDict with a capacity of 12 elements. Each element stores a pointer to IValue which will be the first element of the linked list for that has key. • Value List – an array named IValue with a capacity of 1000 (assume 1000 employees max). Each element stores a value that represents an Employee ID. • Pointer List – an array named IPtr with a capacity of 100. Each element stores a pointer to the next element in IValue that has the same hash key. hDict 0 1 2 3 4 5 6 7 8 9 10 11 IValue IPtr 1 2 4 4 6. 7 8. 10 11 3.
Generate pseudocode for searching for an Employee ID
I was given this example but I don't understand what it means
an employee ID (123) is hashed into a value of 5. For hDict(5) we store a
pointer to the first available spot in lValue, which at the time of the insertion was 2. We store a value of
123 in lValue(2) and a value of null in lPtr(2) because there are no other elements right now, so we
terminate the linked list. Later on another employee ID (135) needs to be inserted. It’s hash value is
also 5. In order to find where to insert it in lValue we need to traverse the linked list to get to the last
element. The first element we come to is 2. lPtr(2) is null so we know we’re at the end of the linked list.
So we get the next empty slot in lValue, which was 3, and assign the value 3 to lPtr(2). We assign the
new Employee ID (135) to next open slot lValue(3) and set lPtr(3) to null because it now becomes the
end of the list.
As the hdict is pointing to lvalue which stores the Employee ID, we have to first find hash value of Employee ID. Then we have to check the pointed lvalue is the ID which we are searching. If not matching, then go to the next lvalue by lPtr pointer since the ID is inserted in the next empty slot in linked list. Continue the process until the ID searched is found. If we reaches null pointer while searching, then the Employee ID is not present.
Step by step
Solved in 2 steps
