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

This article focuses on "how to write advanced java programming HashMap code", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let the editor take you to learn "how to write advanced java programming HashMap code"!

What is HashMap?

In this lesson, we will handwrite a simple HashMap, the so-called HashMap, is a mapping table.

For example, now I have a customer class, just use the previous one.

Now I have 100 clients with different names, some are called Zhang San, some are called Li Si, and some are called Zhang Quanye. If you were to find a man named Wang Nima among these 100 people now, what would you do?

It seems very simple. Didn't we just make a TuziLinkedList? How about going into add one by one, initializing the data, and then traversing it with foreach? However, this efficiency is very low, and if Wang Nima happens to be at the end of the linked list, it will take 100 times to find it. The complexity is o (n)

At this time, if only there was a way for us to find Wang Nima through name at once.

In fact, there is this way, that is, the look-up table method, what we need is such a mapping table.

The mapping table is divided into key and value, and in this case, key is the name field. In this way, the complexity is o (1), which only needs to be traversed once.

To put it simply, no matter how much data you have, if you use the relational mapping table Map, you only need to get the corresponding Customer object directly through a key once.

Why is it so amazing?

That's because the bottom layer of Map is an array.

What is an array?

The knowledge of array is relatively basic, and it has been poorly talked about on the Internet. Just refer to the rookie tutorial directly:

Https://www.runoob.com/java/java-array.html

Because the array directly uses the numerical subscript to get the corresponding value, the complexity is the lowest, which is why the Map query is so fast.

We're going to do a mapping table that looks something like this.

Public class TestMap {public static void main (String [] args) {Map csts = new HashMap (); csts.put (Wang Da Hammer, new Customer (Wang Da Hammer)); csts.put (Wang Nima, new Customer (Wang Nima); csts.put (Zhao Tiezhu, new Customer (Zhao Tiezhu)) / / get the corresponding entity object Customer customer = (Customer) csts.get ("King sledgehammer") directly according to name; System.out.println (customer.getName ());}}

This is the HashMap that comes with java, and we need to implement similar functionality.

HashCode and array

Consider the first question first. Since arrays are used at the bottom of HashMap, but key is not necessarily a number, you have to find a way to convert key to a number.

HashCode is a hash code value. Any string and object has its own hash code, which is calculated as follows:

S [0] * 31 ^ (nmur1) + s [1] * 31 ^ (nMur2) +. + s [n-1]

Use the int algorithm, where s [I] is the first character of the string, n is the length of the string, and ^ represents the exponentiation. The hash value of the empty string is 0.

For example, if the string is "abc", the formula is calculated as follows:

String a = "abc"; / / 97 * 31 ^ (3-1) + 98 * 31 ^ (3-2) + 99 ^ (3-3) / / = 93217 + 3038 + 99 = 96354System.out.println (a.hashCode ())

The answer is:

In 99% of our cases, the key of HashMap is String, so we can use this formula to calculate. The power of the HashCode algorithm is that any string can correspond to a unique number.

I believe you must have a doubt, that is, why the Hash algorithm uses the idempotent operation of 31?

Page 42 of the masterpiece Effective Java explains why hashCode adopted 31:

31 is used because it is an odd prime. If the multiplier is even and the multiplication overflows, the information is lost because multiplying with 2 is equivalent to a shift operation (low complement 0). The benefits of using primes are not obvious, but it is customary to use primes to calculate hash results. 31 has a good performance, that is, using shift and subtraction instead of multiplication, you can get better performance: 31 * I = = (I capacity) {enlarge ();} / / 1\. Calculate HashCode int hashCode = hash (key); / / 2\. Take the module directly to get the remainder, which is the subscript of the array int index = indexForTable (hashCode); / / 3\. Put the corresponding data into the corresponding grid if of the array (this.arr [index] = = null) {this.arr [index] = new LinkedList ();} LinkedList linkedList = this.arr [index]; if (linkedList.size () = = 0) {linkedList.add (key,value);} / / traverse the linked list of the node, and if duplicate key is found, directly overwrite Node firstNode = linkedList.firstNode; Node node = firstNode While (node! = null) {if (node.key.equals (key)) {node.data = value;} node = node.next;} this.size++; return value;} so far, I believe you have a deeper understanding of "how to write advanced HashMap code for java programming". You might as well do it in practice! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.