浅谈java类集框架和数据结构(1)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

在另外一篇博客我简单介绍了java类集框架相关代码和理论。

这一篇博客我主要分析一下各个类集框架的原理以及源码分析。

一：先谈谈LinkedList

这是LinkedList源码的开头，我们能看到几点，1.它的继承关系，实现了哪些接口，Deque<E>就是Quene队列的子类.

2.他的Node属性都是transient关键字，transient即代表在串行化的时候不会持久化数据，LinkedList是实现了序列化接口的，但是这个transient关键字决定了在串行化过程中Node的结果。

继续往下看:

上面代码是我写的测试方法，调用main方法的代码就不展示了，这样比较直观的对应输出关系。

可以看到Collection<E>类集List<E> 的add方法种类，这里选择LinkedList进去看源码。

add调的是linkLast方法，现在我来解释一下这个方法。

LinkedList在add添加元素的时候调用了这个方法，这个方法的意思是：

首先介绍一下Node节点这个数据结构，含有前(prev) 值(element) 后(next)，这三个属性，我习惯称为火车头，数据，火车尾

当添加元素的时候，如果是第一个头元素(l==null，l代表火车尾)，Node的first节点就是该元素，如果火车尾不是空的，也就是代表火车尾挂着一个节点，那么就讲这个元素挂到next节点，像挂火车那样挂。

这里要注意的是链表的数据结构是会挂一个空车厢做车头,也就是说第一次add的元素就会做第一节车厢，接下来判断last都不为空，那么都一节一节往后挂车厢，这就是链表的数据结构，其余的方法看我贴的代码应该可以理解，注释的很细。

二：谈谈HashMap

这个图是我刚才网上截下来的，这也是大家看到最多的hashmap的数据结构，没错就是个table数组挂链表，“链表散列”数据结构，其实原理也很容易解释，在table数组上有很多的位置，每个位置都是一个entry，每个位置就是一个burket篮子，放entry用的。

entry保存的就是key value的建值对，这就是hashmap的数据结构，那么实现这个数据结构的原理就是利用hash算法进行burket的确定，利用hash算法决定这条建值对存放在哪一个篮子里面，如果hashcode冲突的情况下进行equals方法的比较，如果hashcode一样且equals也相等，就在数组的基础上挂链表，解决hash冲突问题。