A lookup in a Hash table is space for time, so what is space for time? For example, if you look for 10000, it is stored in arR [10000], and the subscript of the value is what it is stored in. This wastes a lot of space in exchange for quick searches. What is a Hash collision? For example, if you want to store the number 15 in an array of length 13, it is stored like this: 15%13=2. The number 15 is stored in arr[2]. So when the numbers mod 13 to 2 are also placed at a[2], the Hash collision will occur and the linked list will follow.
The default load factor is 0.75 (data size/array size up to 75%). When the load factor reaches 0.75, a new array with double capacity is created, and all data is re-hashed into the new array.
After Jdk1.8, when the list length reaches 8, the tree will change to red black, and when the tree length decreases to 6, the tree will go back to the list. HashMap adds red-black trees to deal with the problem of inefficient queries when lists are too long.
The initial capacity of Hashtable is 11, and the expansion method is 2N+1.
The initial capacity of HashMap is 16, and the expansion method is 2N.
Why is the loading factor 0.75?
The compromise between improving space utilization and reducing query cost is mainly poisson distribution, 0.75 collision minimum
What is the Poisson distribution? Huh? Go and see the Theory of Probability for yourself!
Take a look at the brain map:
Java collections are divided into value(Collection) and key-value(Map).
List is ordered and repeatable
ArrayList
Advantages: The underlying data structure is an array, fast query, slow add and delete.
Disadvantages: Thread insecurity, high efficiency
Vector
Advantages: The underlying data structure is an array, fast query, slow add and delete.
Disadvantages: Thread safety, low efficiency
LinkedList
Advantages: The underlying data structure is linked list, slow query, fast add and delete.
Disadvantages: Thread insecurity, high efficiency
Set unordered, unique
HashSet
The underlying data structure is a hash table. (Disordered, unique)
How can we ensure element uniqueness?
1. Rely on two methods: hashCode() and equals()
LinkedHashSet
The underlying data structures are linked lists and hash tables. (FIFO insert in order, unique)
1. The order of elements is guaranteed by linked lists
2. Hash tables ensure that elements are unique
TreeSet
The underlying data structure is a red-black tree. (Unique, ordered)
- How do you make sure the elements are sorted?
Natural sort, comparator sort
2. How to ensure the uniqueness of elements?
Depending on whether the return value of the comparison is 0