一帆磨砺

生活所迫,一叶孤舟

0%

写在开头

  1. 扩容是一个特别耗性能的操作,因此建议使用HashMap时,尽量指定一定大小的初始容量
  2. HashMap是线程不安全的,并发环境中建议使用ConcurrentHashMap
  3. JDK8中引入的红黑树优化了大量hash碰撞时的性能
  4. HashMap中的红黑树代码作者实在没力气看了,因此这篇文章不涉及内部红黑树分析
  5. 该篇文章纯粹是作者个人观点,并非官方权威,阅读请勿迷信
    Read more »

Tips:

  1. 红黑树是搜索二叉树的变种,可以先行理解AVLTree
  2. 根据多方资料查找,很多人说2-3树和2-3-4树有助于理解红黑树(个人未进行深入了解,有兴趣可以自行搜索相关资料,或者等我再一次诈尸) 红黑树是2-3-4树的一种等同。换句话说,对于每个2-3-4树,都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具,这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因,尽管2-3-4树在实践中不经常使用。 (wiki)
  3. 红黑树与AVL树不同,不具备部分AVL树的特性,如:每个节点的左右节点的高度差值不超过1
  4. 关于为什么新增节点一定是红色,个人未找到合理解释(目前仅理解为红色可以避免部分需要修复的情况),可能会在2-3-4树中找到原因

demo代码
主要参考于TreeMap

Read more »

Tips:

  1. 如果要在集合中使用自定义类,建议重写equals函数
  2. 如果集合内元素较多,使用结束后建议清空(GC)
  3. LinkedList所提供的原生函数无批处理,所以会有线程安全的假象,但是它并非线程安全,并且因为不想ArrayList提供批处理函数(函数内针对线程安全做了一定的处理),所以在使用LinkedList时需要格外注意
  4. 链表核心在于指针(即引用),可以先行了解这部分
  5. 本次未像ArrayList提供基础代码调用实现
    Read more »

Tips:

  1. 如果要在集合中使用自定义类,建议重写equals函数
  2. 如果集合内元素较多,使用结束后建议清空(GC)
  3. BitSet
  4. ArrayList是非线程安全的
    Read more »