After a hashmap source code analysis-CodePudding

Version: jdk1.8
1, why hashmap array + list of linked list data structure is not a two-way linked list?
2, why put operation is added after the 1.8 1.7 is a linked list at the end of the list of add new element is red and black head binary tree effect

CodePudding user response:

1, after the hash conflict, continue to start from list traversal is equals, don't need a two-way
2, because the insert of the head, then concurrent situation will appear dead circulation

CodePudding user response:

reference 1st floor kse_music response:

1, the hash conflict, continue to start from list traversal is equals, don't need a two-way
2, because the insertion of the head, and then the concurrent situation will appear dead cycle

1, the list is not delete this efficiency to solve the new insert delete two-way linked list is not faster
2, concurrent hashmap unsafe to use don't have to lock or use concurrenthashmap

CodePudding user response:

refer to the second floor tcme209 response:

Quote: refer to 1st floor kse_music response:

1, after the hash conflict, continue to start from list traversal is equals, don't need a two-way
2, because the insertion of the head, and then the concurrent situation will appear dead cycle

1, the list is not delete this efficiency to solve the new insert delete two-way linked list is not faster
2, concurrent hashmap unsafe to use don't have to lock or use concurrenthashmap

1, if the list is long, the time complexity becomes O (n), while the red-black tree is O (logn), is a kind of balance, right, so when elements of more than 64 in 1.8 and the chain length of the table into the red-black tree is greater than 8, when less than 6 will degenerate into a list
2,1.7 when inserted with head is considered one of the so-called hot spots data point (the newly inserted data may be used earlier), but it is a false proposition, y because JDK1.7 rehash when, in the old list time to move the new list, if the same position in the new table array index, then the list elements will be upside down (because of his head) so the final result or disrupted the order of the insert so overall support 1.7 use head put this reason is not enough to support any longer so simply to end inserted fully staffed personal understanding

CodePudding user response:

reference kse_music reply: 3/f

Quote: refer to the second floor tcme209 response:

Quote: refer to 1st floor kse_music response:

1, after the hash conflict, continue to start from list traversal is equals, don't need a two-way
2, because the insertion of the head, and then the concurrent situation will appear dead cycle

1, the list is not delete this efficiency to solve the new insert delete two-way linked list is not faster
2, concurrent hashmap unsafe to use don't have to lock or use concurrenthashmap

1, if the list is long, the time complexity becomes O (n), while the red-black tree is O (logn), is a kind of balance, right, so when elements of more than 64 in 1.8 and the chain length of the table into the red-black tree is greater than 8, when less than 6 will degenerate into a list
2,1.7 when inserted with head is considered one of the so-called hot spots data point (the newly inserted data may be used earlier), but it is a false proposition, y because JDK1.7 rehash when, in the old list time to move the new list, if the same position in the new table array index, then the list elements will be upside down (because of his head) so the final result or disrupted the order of the insert so overall support 1.7 use head put this reason is not enough to support any longer so simply to end inserted fully staffed personal understanding

Understand a little bit, tangled chain table structure forget key and contrast, still and 1.8 reference tree also has something to do, if it's head, a traverse of the look have the same, if not, eighth elements and tree times lixia, affect the efficiency, tail plug tree is directly in the tail