Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "how to realize the Hash table". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1. What is Hash table

Hash, generally translated as "hash" and directly transliterated as "hash", is designed from the point of view of fast access, and it is also a typical practice of "space for time". As the name implies, the data structure can be understood as a linear table, but the elements in it are not closely arranged, but there may be gaps.

A hash table (Hash table, also known as a hash table) is a data structure that is accessed directly based on key code values (Key value). That is, it accesses the record by mapping the key value to a location in the table to speed up the lookup. This mapping function is called a hash function, and the array in which records are stored is called a hash table. For example, we store 70 elements, but we may have applied for 100 elements for these 70 elements. This number is called the load (load) factor. We do this for the purpose of "quick access". We arrange the storage location for each element based on a fixed function H whose results are randomly and evenly distributed as far as possible to achieve fast access. But because of this randomness, it will inevitably lead to a problem, that is, conflict. The so-called conflict means that two elements get the same address through the hash function H, so the two elements are called "synonyms". This is similar to 70 people going to a restaurant with 100 chairs for dinner. The hash function evaluates to a storage unit address, each of which is called a "bucket". If there are m buckets in a hash table, then the range of the hash function should be [05m MMI 1].

According to what rules are these elements stored in the array? In general, it is obtained through hash (key)% len, that is, the hash value of the element's key is obtained by modulating the length of the array. For example, in the above hash table, "1214012" is 28" 12108 ". So 12, 28, 108, and 140 are all stored in the array subscript 12.

Understanding of capacity expansion of 2.hash Table

However, when the hash table is nearly full, the performance is low (transferred to a larger hash table) because of the expansion of the array.

The default hash cell size of Java is all to the power of 2, with an initial value of 16 (the fourth power of 2). If 75% of the 16 linked lists have data, the load factor is considered to be 0.75 by default. HahSet begins to rehash, that is, to discard all the original hash structure, reopen a hash result with a hash unit size of 32 (to the fifth power of 2), and recalculate the storage location of each data. And so on.

Load (load) factor: 0.75. The space provided by the hash table is 16, which means the capacity will be expanded when it reaches 12.

3. The realization of weight arrangement mechanism

If we have a data (hash code 76268), and the HashSet has 128 hash units, then this data will probably be inserted into the 108th linked list of the array (762688x108). But this is only possible, if an old data and new data equals () = true are found in the 108 linked list, the new data will be considered to have been added and will not be repeatedly thrown into the linked list.

4. Advantages

The insertion and lookup of hash tables are excellent.

For lookup: after calculating the remainder directly based on the hash code of the data and the array size of the hash table, you can get the location of the array, and then find out if there is this data in the linked list. Because the search speed of the array itself is fast, the search efficiency is reflected in the linked list, but in real life, there is little or no data in a linked list, so there is almost no iterative cost. Therefore, the search efficiency of the hash table is based on the amount of data in the linked list that the hash unit points to.

For inserts: array inserts are slow, while linked lists are fast. When we use the hash table, we don't need to change the structure of the array, we just need to find the corresponding array subscript, enter the corresponding linked list and manipulate the linked list. So the overall insertion speed of the hash table is also very fast.

5. Simulation implementation code

Node class

`

Public class Node {

/ / key and value simulate the data of key-value pairs

Public Integer key

Public String value

/ / reference to the next node

Public Node next

Public Node () {

}

Public Node (int key, String value) {

This.key = key

This.value = value

}

}

`

MyLinkedList class

`

Public class MyLinkedList {

/ / Root node

Private Node root

Public MyLinkedList () {

Root = new Node ()

}

/ * *

* add data, the key value must be unique, if the duplicate value will be overwritten

* @ param key

, /

Public void add (int key, String value) {

Node newNode = newNode (key, value)

Node current = root

While (current.next! = null) {

If (current.next.key = = key) {

Current.next.value = value

Return

}

Current = current.next

}

Current.next = newNode

}

/ * *

* Delete data

* @ param key

* @ return

, /

Public boolean delete (int key) {

Node current = root

While (current.next! = null) {

If (current.next.key = = key) {

Current.next = current.next.next

Return true

}

Current = current.next

}

Return false

}

/ * *

* obtain value based on key

* @ param key

* @ return

, /

Public String get (int key) {

Node current = root

While (current.next! = null) {

If (current.next.key = = key) {

Return current.next.value

}

Current = current.next

}

Return null

}

/ * *

* iterate through the linked list to list all the data

* @ return

, /

Public String list () {

String str = ""

Node current = root.next

While (current! = null) {

Str + = "(" + current.key + "," + current.value + "),"

Current = current.next

}

Return str

}

@ Override

Public String toString () {

Return list ()

}

}

`

MyHashMap class

`

/ / Hash table

Public class MyHashMap {

/ / linked list array, each item in the array is a linked list

Private MyLinkedList [] arr

/ / size of the array

Private int maxSize

/ * *

* empty parameter construction. The default array size is 10.

, /

Public MyHashMap () {

MaxSize = 10

Arr = new MyLinkedList [maxSize]

}

/ * *

* Construction with parameters, and custom array size

* @ param maxSize

, /

Public MyHashMap (int maxSize) {

This.maxSize = maxSize

Arr = new MyLinkedList [maxSize]

}

/ * *

* add data, the key value must be unique

* @ param key

* @ param value

, /

Public void put (int key, String value) {

Int index = getHashIndex (key)

If (arr [index] = = null) {

Arr [index] = new MyLinkedList ()

}

ARR [index] .add (key, value)

}

/ * *

* Delete data

* @ param key

* @ return

, /

Public boolean delete (int key) {

Int index = getHashIndex (key)

If (arr [index]! = null) {

Return arr [index] .delete (key)

}

Return false

}

/ * *

* obtain value based on key

* @ param key

* @ return

, /

Public String get (int key) {

Int index = getHashIndex (key)

If (arr [index]! = null) {

Return arr [index] .get (key)

}

Return null

}

/ * *

* get array subscript

* @ param key

* @ return

, /

Private int getHashIndex (Integer key) {

Return key.hashCode () maxSize

}

/ * *

* traverse the data of all linked lists in the array

* @ return

, /

Public String list () {

String str = "["

For (int I = 0; I < maxSize; iTunes +) {

If (ARR [I]! = null) {

Str + = arr [I] .toString ()

}

}

Str = str.substring (0, str.length ()-1)

Str + = "]"

Return str

}

@ Override

Public String toString () {

Return list ()

}

}

`

Test class

`

Public class Test {

Public static void main (String [] args) {

MyHashMap map = new MyHashMap (20)

Map.put (5, "aaa")

Map.put (8, "bbb")

Map.put (3, "ccc")

Map.put (8, "bbb")

Map.put (2, "ddd")

Map.put (9, "eee")

System.out.println (map)

System.out.println (map.get (3))

System.out.println (map.delete (2))

System.out.println (map)

}

}

This is the end of the content of "how to implement Hash Table". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.