Java collections source code learning note

Posted on Edited on

Summary

https://docs.google.com/spreadsheets/d/1RrJplFDo4eUL97iUsypflmbEnVFG2VhLAe-VERYTwzg/edit?usp=sharing

Reference

1 HashMap

Short description Link
Time Complexity of HashMap methods https://stackoverflow.com/questions/4577998/time-complexity-of-hashmap-methods
Time Complexity of HashMap get() https://skyfly.xyz/2020/02/25/Java/HashMapTimeComplexity/
Understanding HashMap resize() https://segmentfault.com/a/1190000015812438
The main document that I learn HashMap https://blog.csdn.net/v123411739/article/details/78996181
Another document contains some interview questions https://blog.csdn.net/v123411739/article/details/115364158
A document with illustration (need to login CSDN) https://blog.csdn.net/yinwenjie/article/details/102531402

Questions:

  • Didn’t clearly learn the remove() method.
  • For the tableSizeFor(), it is changed after java 8. But I don’t know how to locate the version of a code change.
  • After the sharing
    • The actual binary calculation progress of the capability of Map. For example capability is 32, so binary is what?
      • For example, 111 is 7. But 7 cannot be the capacity.
    • What is amortized time complexity?

Problems solved:

  • The difference between (n - 1) & hash and (e.hash & oldCap) == 0 by reading Understanding HashMap resize().
  • The time complexity for put() get() delete() is from O(1) to O(k), the key can be a bin’s Linked List or the height of the red black tree.

2 ArrayList

Short description Link
A main document that I’ve studied https://blog.csdn.net/zxt0601/article/details/77281231
Another ArrayList docs that I didn’t read too much https://blog.51cto.com/u_13604316/2673349

Questions:

  • Will System.arrayCopy got overlap? In linux, there are 2 way to copy the memory, one of them can cause overlap and data loss.
  • Will ArrayList shrink?
  • What is System.arrayCopy’s space complexity?

Problem solved:

  • How ArrayList insert an value?
    • grow() -> System.arrayCopy the second half -> Insert the target value to the middle empty slot

3 LinkedList

Short description Link
A main document that I’ve studied https://blog.csdn.net/zxt0601/article/details/77341098

Questions:

  • Why LinkedList didn’t implement the isEmpty() method directly?

Problem solved:

  • How LinkedList treat the value that is null?
    • LinkedList can find the index based on the keyObject.equals(). For example, LinkList.indexOf(Object o). When we input indexOf(null), it need to avoid calling null.equals(). And use == instead.
    • LinkedList.contains() also calls indexOf(Object o)

4 PriorityQueue

Short description Link
PriorityQueue source code analysis doc with a little problem https://blog.csdn.net/codejas/article/details/85144502

This PriorityQueue source code analysis doc with a little problem has a problem of saying that PriorityQueue is min-heap. But actually, the PriorityQueue is max heap.