Hash Table data structure

What is Hash Table?

The Hash Table data structure is a data structure that stores data in a federated manner. In Hash Table, data is stored in array format, in which data values ​​have their own index values. Accessing data becomes faster if we know the index of the data to find.

Therefore, with this type of Hash Table data structure, insertion and search operations will take place very quickly, regardless of the size of the data. Hash Table uses arrays as an intermediate repository and uses hash techniques to create indexes where elements are inserted.

Hashing techniques

Hashing is a technique to convert a range of key values ​​into a range of index values ​​of an array. We are using the remainder operator to obtain a sequence of key values. Suppose there is a HashTable of size 20, and below are the elements that need to be stored. Element in format (key, value).

Hash Table data structure Picture 1

(1.20)
(2.70)
(42.80)
(4.25)
(12.44)
(14.32)
(17.11)
(13.78)
(37.98)

SttKeyHash Array index1 1 1% 20 = 1 1 2 2 2% 20 = 2 2 3 42 42% 20 = 2 2 4 4 4% 20 = 4 4 5 12 12% 20 = 12 12 6 14 14% 20 = 14 14 7 17 17% 20 = 17 17 8 13 13% 20 = 13 13 9 37 37% 20 = 17 17

Linear Probing Technique (Linear Probing)

We see that it is possible that the hashing technique used to create an index already exists in the array. In this situation, we need to search for the next blank position in the array by looking in the next cell until we find an empty cell. This technique is called Linear Probing.

SttKeyHash Only array itemAfter technique Linear Probing, array index1 1 1% 20 = 1 1 1 2 2 2% 20 = 2 2 2 3 42 42% 20 = 2 2 3 4 4 4% 20 = 4 4 4 5 12 12% 20 = 12 12 12 6 14 14% 20 = 14 14 14 7 17 17% 20 = 17 17 17 8 13 13% 20 = 13 13 13 9 37 37% 20 = 17 17 18

Basic operations on Hash Table

Here are some basic operations that can be performed on the Hash Table data structure.

Search activity : search for an element in the HashTable data structure.

Insert operation : insert an element into the HashTable data structure.

Delete operation : delete an element from the HashTable data structure.

Data Element (DataItem) in HashTable

Data elements include: data and key. Based on this key we can perform search operations in the HashTable data structure.

 struct DataItem { int data ; int key ; }; 

Method of Hash Table data structure

Specify a method to estimate the Hash Code of the key of the data element.

 int hashCode ( int key ){ return key % SIZE ; } 

Search activity in Hash Table

Each time an element is searched: estimate the hash code of the transmitted key and then determine the element's location using that hash code value as an index in the array. Use Linear Probing to get the element if no element is found with the estimated hash code value.

 struct DataItem * search ( int key ){ //lấy giá trị hash int hashIndex = hashCode ( key ); //di chuyển trong mảng cho tới khi gặp ô trống while ( hashArray [ hashIndex ] != NULL ){ if ( hashArray [ hashIndex ]-> key == key ) return hashArray [ hashIndex ]; //tới ô tiếp theo ++ hashIndex ; //bao quanh hash table hashIndex %= SIZE ; } return NULL ; } 

Insert operation in Hash Table

Each time an element is inserted: estimate the hash code of the transmitted key and determine the element's location using that hash code value as an index in the array. Use Linear Probing for the blank position if the element is found with the estimated hash code value.

 void insert ( int key , int data ){ struct DataItem * item = ( struct DataItem *) malloc ( sizeof ( struct DataItem )); item -> data = data ; item -> key = key ; //Lấy giá trị hash int hashIndex = hashCode ( key ); //di chuyển trong mảng cho tới khi gặp ô trống hoặc bị xóa while ( hashArray [ hashIndex ] != NULL && hashArray [ hashIndex ]-> key != - 1 ){ //tới ô tiếp theo ++ hashIndex ; //bao quanh hash table hashIndex %= SIZE ; } hashArray [ hashIndex ] = item ; } 

Delete operation in Hash Table

Whenever an element needs to be deleted: estimate the hash code of the transmitted key and then determine the element's location using that hash code value as an index in the array. Use Linear Probing to get the element if no element is found with the estimated hash code value. Once found, store a fake element here to keep the hash table's performance.

 struct DataItem * delete ( struct DataItem * item ){ int key = item -> key ; //lấy giá trị hash int hashIndex = hashCode ( key ); //di chuyển trong mảng cho tới khi gặp ô trống while ( hashArray [ hashIndex ] != NULL ){ if ( hashArray [ hashIndex ]-> key == key ){ struct DataItem * temp = hashArray [ hashIndex ]; //gán một phần tử giả tại vị trí bị xóa hashArray [ hashIndex ] = dummyItem ; return temp ; } //tới ô tiếp theo ++ hashIndex ; //bao quanh hash table hashIndex %= SIZE ; } return NULL ; } 

According to Tutorialspoint

Previous article: Interpolation Search algorithm (Interpolation Search)

Next lesson: Alignment algorithm in data structure & algorithm

4 ★ | 1 Vote

May be interested

  • Heap data structureHeap data structure
    data structure the heap is a special case of a balanced binary tree data structure, where the root node's key is compared to its children and arranged accordingly.
  • MS Access 2003 - Lesson 12: Working with a tableMS Access 2003 - Lesson 12: Working with a table
    you have learned how to create and design tables in access. and now it's time to learn how to manipulate all tables.
  • Structure (Struct) in C programmingStructure (Struct) in C programming
    arrays in c allow you to define several types of variables that can hold the values ​​of several components of the same type. but the structure is another type of data in the c programming language, which allows you to combine other types of data.
  • List of file names, HASH SHA-256 codes containing WannaCry malwareList of file names, HASH SHA-256 codes containing WannaCry malware
    ransomeware wannacry is currently the most confusing ransomware. once you have been infected with wanna cry malware, you are forced to pay the amount from 300 dollars to decrypt the data. so, if you don't want to lose money unjustly, let's take preventive measures such as deleting files named in the file name list, hash sha-256 code containing wanna cry malware through the list of repair file names. wannacry malware below.
  • Graph data structure (Graph)Graph data structure (Graph)
    a graph (graph) is a form of visual representation of a set of objects in which pairs of objects are connected by links. interconnected objects are represented by points called vertices, and links that connect vertices are called edges.
  • How to fix status_​invalid_​image_​hash error on Microsoft EdgeHow to fix status_​invalid_​image_​hash error on Microsoft Edge
    your favorite browser is microsoft edge, but you always feel annoyed when you are surfing the web and there is a status_​invalid_​image_​hash error. please click on the article to find out how to fix the status_​invalid_​image_​hash error.
  • What is the Master Partition Table?What is the Master Partition Table?
    the master partition table is a component of the master boot record / sector that describes the partitions on the hard drive, such as their type and size, and comes with the disk signature and the master boot code to create the master boot record.
  • What is the best URL structure for SEO?What is the best URL structure for SEO?
    many visitors will reach your website by clicking on a link, so you might be wondering if what's in the url of a particular page is really important.
  • Collection in C #Collection in C #
    collection classes are special classes for storing and retrieving data. these classes provide support for stack, queue, list, and hash table. most collection classes in c # deploy the same interface.
  • The hash () function in PythonThe hash () function in Python
    the hash () function in python returns the hash value of the object (if any).