Shulou(Shulou.com)05/31 Report--

In this article Xiaobian for you to introduce in detail "JavaScript data structure hash table how to create", the content is detailed, the steps are clear, the details are handled properly, I hope this "JavaScript data structure hash table how to create" article can help you solve doubts, following the editor's ideas slowly in-depth, together to learn new knowledge.

First, deal with hash value conflicts

Sometimes some keys have the same hash value. For example, aab and baa are different values from a string point of view, but according to our hash function logic, the hash value from the Unicode code of each letter must be the same.

We know that in the JavaScript object, if the key specified at the time of assignment already exists, then the original value will be overwritten, such as this example:

Var json = {18: 'Leo'} json [18] ='Ob 'console.log (json) / / {18:' Ob'}

In order to avoid the risk in the above code, we need to figure out how to deal with it. How to make key! = key, then hash! = hash?

At present, there are two reliable methods, namely, separating links and linear probing.

1. Detach link

The detached link method means that when storing data in a hash table, the value part replaces the previous key-value pair with a linked list. Only one key-value pair can be stored, while a linked list can store multiple key-value pairs. If you encounter the same hash value, you can add a key-value pair to the existing linked list.

We need to rewrite three methods: put, get, and remove. Let's see how to achieve:

Class HashTableSeparateChaining {constructor () {this.table = {} 2.put method

First, the basic class structure, then look at the put method:

Put (key, value) {if (key! = = null & & value! = = null) {let pos = this.hashCode (key) if (! this.table [pos]) {this.table [pos] = new LinkedList ()} this.table [pos] .push (new ValuePair (key, value) return true;} return false;}

The LinkedList class is a standard linked list class, which is described in the linked list section and is directly used here.

Compared with the hash table put method in the previous article, you will find that there is little difference, and the changes are as follows:

/ / this.table [pos] = new ValuePair (key, value) / / after change if (! this.table [pos]) {this.table [pos] = new LinkedList ()} this.table [pos] .push (new ValuePair (key, value))

The optimized logic is that when storing data, key-value pairs are stored in a linked list. If there is the same hash value, a key-value pair is added to the existing linked list, thus avoiding overwriting.

However, this approach also has a drawback, each time a key-value pair is added, a linked list is created, which adds extra memory space.

3.get method

Get method:

Get (key) {let linkedList = this.table [this.hashCode (key)] if (linkedList & &! linkedList.isEmpty ()) {let current = linkedList.getItemAt (0); while (current) {if (current.value.key = = key) {return current.value.value} current = current.next}} return undefined;}

The new get method is obviously much more complex than the previous one. The main logic is to find a linked list based on key, then traverse the list to find the key-value pair that matches the parameter key, and finally return the found value.

Using return in the while loop can directly abort the current function.

After reading this, the article "how to create a hash table of JavaScript data structures" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it yourself to understand it. If you want to know more about related articles, welcome to follow the industry information channel.

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.