読者です 読者をやめる 読者になる 読者になる

About HashTable in Java

HashMap Collision

What’s HashMap

HashTable is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array.

Hash table - Wikipedia

Structure Of HashMap in Java

HashMap class in java has array internally to save objects. The objects are Nodes that have key and value.

https://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Hash_table_3_1_1_0_1_0_0_SP.svg/630px-Hash_table_3_1_1_0_1_0_0_SP.svg.png

Hash Function

HashMap has a Hash Function. This function computes the index from inputted key.

Hash Collision

HashTable has a problem. When it computes the index by hash function, the results value of hash function can be identical. This phenomenon is called as Collision. In java, if collision occurs, the object is linked with a node has same index. Therefore, each node in array has Binary Search Tree.

http://coding-geek.com/wp-content/uploads/2015/03/internal_storage_java8_hashmap.jpg

coding-geek.com