Map--HashMap--TreeMap--红黑树
Map:三种遍历方式
HashMap:拉链法。用哈希函数计算出int值。
用桶的思想去存储元素。桶里的元素用链表串起来,之后长了的话转红黑树。
TreeMap:红黑树。
所以看Map的源码就是把红黑树给拿下。
红黑树
插入:前面找插入位置完全同二叉搜索树
插入调整
删除
删除调整
以上代码图都是基于:
http://www.cnblogs.com/skywang12345/p/3245399.html 红黑树原理
http://www.cnblogs.com/skywang12345/p/3624343.html 红黑树代码实现
啃红黑树之前最好先看看二叉搜索树,把搜索弄懂 http://www.cnblogs.com/skywang12345/p/3576452.html 二叉搜索树
还可以看看这个大神的AVL树,把四种旋转看懂再看红黑树的旋转就简单了。
红黑树的插入比较好理解,删除的四种调整我不是很理解为什么要这么调整,但是结合图又让我感觉就是这么一回事。