数据结构及其应用

【数据结构】：

啊哈，相信大家或多或少都接触了一些。线性数据结构lArrayList  and  LinkedList

                                                                 非线性数据结构 HashSet  and  HashMap

今天提到这四个呢，并不是讲这几个怎么用，而是提出一个问题，为什么那么多大型公司面试官这么喜欢问这四个，这么喜欢比较他们的区别呢，我在面试阿里的时候这个基本是每一面都要提到的，区别，区别，情景模拟怎么用，哪些数据结构用到？我们来慢慢引出？首先讲一下他们的特性，以及怎么用？

===================================================================================

【ArrayList】：

    数组列表  线性数据结构，可以在任何位置对元素进行增删查改。

但是：

• ArrayList是非同步的。在多线程并发操作ArrayList场景下，需要我们写代码对ArrayList进行同步
• ArrayList是利用数组实现的，本身可以看做是一个动态的数组，对元素增删都会引起数组内存分配空间动态发生变化，所以插入，删除会比较慢，但是检索速度快。

【看一下方法】：

boolean add(E e)

将指定的元素添加到此列表的尾部。

void add(int index, E element)

将指定的元素插入此列表中的指定位置。

boolean addAll(Collection<? extends E> c)

按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。

boolean addAll(int index, Collection<? extends E> c)

从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。

void clear()

移除此列表中的所有元素。

Object clone()

返回此 ArrayList 实例的浅表副本。

boolean contains(Object o)

如果此列表中包含指定的元素，则返回 true。

void ensureCapacity(int minCapacity)

如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。

E get(int index)

返回此列表中指定位置上的元素。

int indexOf(Object o)

返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。

boolean isEmpty()

如果此列表中没有元素，则返回 true

int lastIndexOf(Object o)

返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。

E remove(int index)

移除此列表中指定位置上的元素。

boolean remove(Object o)

移除此列表中首次出现的指定元素（如果存在）。

protected void removeRange(int fromIndex, int toIndex)

移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。

E set(int index, E element)

用指定的元素替代此列表中指定位置上的元素。

int size()

返回此列表中的元素数。

Object[] toArray()

按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。

<T> T[] toArray(T[] a)

按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。

void trimToSize()

将此 ArrayList 实例的容量调

 

整为列表的当前大小。    

 

 

 

============================================================================

【LinkedList】：

同上

注意：

• 非同步，并发多线程需要自己写代码控制
• 内部是链表实现，因此和ArrayList相比，增删很快，因为list不需要重新分配空间，但是检索速度慢
• 实现了Queue接口，可做先进先出队列使用

 

 

 

 ===============================================================================

【HashMap】

数组

数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；

链表

链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。

       哈希表

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表。哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。

 

 我们来看一组生动的图：

 可以看得出左边是数组，右边是链表的这种结合。

hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

如果两个key通过hash%Entry[].length得到的index相同，会不会有覆盖的危险？

　　这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止，HashMap的大致实现，我们应该已经清楚了。

http://blog.csdn.net/vking_wang/article/details/14166593这个博客讲的更加清楚对Hashmap这个原理，能够看懂。

================================================================================

【HashSet】：

集合类型数据结构，实现了set的接口，满足数学定义，无序，不重复。

• 非同步，多线程并发需要自己写代码
• Hashset内部由HashMap实现，对元素增删查也有很高性能
• 元素无序，对其遍历，不保证顺序都一致，也就是说每一次打印出来的元素位置都不一样
• 没有重复元素，加入相同的对象到hashset里面，则最终hashset里面只有一个对象。