About the hashMap data structure-CodePudding

Just now I was watching a hashmap array structure, see this picture, and then a bit confused?

I look at the picture to understand is that table array [] is the key, and the list is used to save the corresponding value, usually is not a key corresponding to a value, that if a key corresponding to a linked list, the value is corresponding data structure is an arrayList, then when the length of the arrayList storage after more than eight, list the data structure reorganization for red and black tree?
Don't know my understanding right? If there is a problem, please help me to give directions, a little fan,,

CodePudding user response:

Table array [] after the hash computation is the key of to get the value (street), the list is the corresponding key - value of the key/value pair (house number - people), but may have a number of different key after hash calculation to get the value of the same (different people may live in the same street, but is not the same as the house number), so that when we find data (someone), look for the key after the hash calculation to get the value of the streets (find), and then use the equals () to find the corresponding key (house number), and finally found the corresponding data (people)

CodePudding user response:

My understanding is that the table is [] storage & lt; The key, value> , the list is supposed to be a linkList, is mainly used to solve the conflict of the hash, after JDK1.8 list will only be because of the length of restructuring into a red-black tree, because the list query efficiency is too slow, very affect efficiency if the list is long enough

CodePudding user response:

Upstairs said good,
Hash in a given key enough cases, the collision probability is relatively high,
In the hash value of the key phase at the same time, the value is in the array,

Generally small-scale application scenario, the data quantity is not too big, the collision probability almost negligible,
So many articles said HashMap approximate time complexity to O (1)

CodePudding user response:

refer to the second floor opening of a smile to reply:

my understanding is that the table is [] storage & lt; The key, value> , the list is supposed to be a linkList, is mainly used to solve the conflict of the hash, after JDK1.8 list will only be because of the length of restructuring into a red-black tree, because the list query efficiency is too slow, if the list is long enough are affect the efficiency of

 
Map The map=new HashMap<& gt; (a); 
The map. The put (" name ", "* *"); 
The map. The put (" name ", "li si"); 
System. The out. Println (map. Get (" name "));

According to your meaning, this kind of circumstance is in order to solve the conflict of the hash, then zhang SAN, li si is stored in the linkList, if it is, then how to get zhang SAN?

CodePudding user response:

The

reference 3 floor water 2 reply:

upstairs said good,
Hash in a given key enough cases, the collision probability is relatively high,
In the hash value of the key phase at the same time, the value is in the array,

Generally small-scale application scenario, the data quantity is not too big, the collision probability almost negligible,
So many articles said HashMap approximate time complexity to O (1)

in the hash value of the key phase at the same time, the value is in the array,
This sentence you say I am more stupid,,,

CodePudding user response:

reference 4 floor Never compromise response:

Quote: refer to the second floor opening of a smile to reply:
my understanding is that the table is [] storage & lt; The key, value> , the list is supposed to be a linkList, is mainly used to solve the conflict of the hash, after JDK1.8 list will only be because of the length of restructuring into a red-black tree, because the list query efficiency is too slow, if the list is long enough are affect the efficiency of

Map The map=new HashMap<& gt; (a);
The map. The put (" name ", "* *");
The map. The put (" name ", "li si");
System. The out. Println (map. Get (" name "));

According to your meaning, this kind of circumstance is in order to solve the conflict of the hash, then zhang SAN, li si is stored in the linkList, if it is, then how to get zhang SAN?

Completely wrong, you still didn't understand a HashMap, the execution of the map. The put (" name ", "li si"); Later, zhang SAN has been abandoned, has no zhang SAN array,

HashMap, will first calculate the "name". HashCode, then go to find array in the Map, find the array, the array, looking for a "name", if present, is covered, does not exist, is a place at the end of the array insert "name: zhang SAN"

CodePudding user response:

1, Java classic, like the hashMap data structure is best to look at the source code, the table [] array is not the key, but the Node (called entry before jdk1.7), the Node is the chain table structure, namely table [] is a linked list, Node has three main properties, the key and the value and the hash
2, not list length to 8 will be the tree, there is a condition that the length of the array must be greater than or equal to 64, the tree is to increase the query efficiency, arrive in eight chain length of the table, but when the array length less than 64, a hashMap will be expanded operations, because expansion can reduce the hash conflict, as well as to improve the query efficiency

CodePudding user response:

Don't just look at the picture, it is suggested that adjust the following code study combined with the source code, the following code example is to hash the conflict

 
HashMap The map=new HashMap<& gt; (a); 
//the following key hash values are all the same, the so-called hash collision 
 the condition of theString [] keys={" AaAaAaAa ", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa", 
"BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa," 
"AaBBAaAa", "AaBBBBBB AaBBAaBB", ""," AaBBBBAa, "
"BBAaAaAa", "BBAaBBBB BBAaAaBB", ""," BBAaBBAa, "}; 
for(int i=0; iThe String key=keys [I]; 
System. Out. Println (key + ":" + key. The hashCode ()); 
The map. The put (key, I); 
} 
System.out.println(map);

CodePudding user response:

My understanding is that, I do not know right? When we put the (key, value), the key will be through the hash algorithm mapped to a number, this number is an array of id, such as the put (" name ", "li si"), assuming that "name" of the hash value is 1001, then put (" name ", "li si") is equivalent to the table [1001]=new Object [3]. The table [1001] [0] [0]="name"; Table [1001] [0] [1]="bill", the table [1001] [0] [2]=null, when we name=get (" name "), direct is equivalent to name=table [1001] [0] [1], so it is not to find and obtain data directly, so the time complexity is O (1) at this moment, and when we put again (" name ", "detective"), then id=1001 this unit has been opened, and there is a table [1001] [0] [0]=="name", so this is the table [1001] [0] [1]="detective", "li si", this value has been overwritten, if we put (" cars ", "BMW"), and we suppose to "a multitude" the key's hash value is 1001, because the id=1001 this unit has been opened, and the table [1001] [0] [0]!="cars", so this situation is to hash collision happened, and then we can't table [1001] [0] [0]="cars", table [1001] [0] [1]="BMW", then how to do? That is to build a linked list, namely executive table [1001] [0] [2]=new Object [3], table [1001] [0] [2] [0]="cars", table [1001] [0] [2], [1]="BMW" table [1001] [0] [2], [2]=null, and so on, when the list is too long, took the list into the red-black tree,

CodePudding user response:

In the table of hash value, also is to insert a & lt; K, v> , to take a hash of k, first find a place in the table, and then look at the location of data chain table have the same key, is covered, there have been inserted into the list

CodePudding user response:

reference 4 floor Never compromise response:

Quote: refer to the second floor opening of a smile to reply:
my understanding is that the table is [] storage & lt; The key, value> , the list is supposed to be a linkList, is mainly used to solve the conflict of the hash, after JDK1.8 list will only be because of the length of restructuring into a red-black tree, because the list query efficiency is too slow, if the list is long enough are affect the efficiency of

Map The map=new HashMap<& gt; (a);
The map. The put (" name ", "* *");
The map. The put (" name ", "li si");
System. The out. Println (map. Get (" name "));
nullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnull