Java与数据结构

java 中的数据结构
java中用到的集合有：
list
set
map
首先回顾下计算机中基本的两种物理存储结构：数组和链表
数组：不能扩容，每个元素都有下标，在内存中是一块连续的内存地址，优点：查询速度快时间复杂度O(1),增加和删除元素需要移动被操作元素的后续所有元素，增删的时间复杂度O(N).
链表：动态扩容，每个元素靠首尾指针连接上一个和下一个元素,结点分配在不连续的内存里，优点：增删速度快，时间复杂度O(1),查询速度慢O(N)；
迭代器：集合通常实现了Iterator接口，当使用增强for循环的时候，实际上编译器会转换使用Iterator来遍历集合。Iterator的remove方法比collection的更具有点。两者对集合结构的操作都不可同时进行。因此在增强for循环中不能使用list.remove（x）等操作，在很多操作中更建议使用迭代器来操作，它是每次向前推进一个元素，效率更高，尤其是LinkedList。

list：
arraylist:基于数组实现，有序，能扩容，通过数组copy将数据到新的数组，线程不安全。
linkedlist：基于链表实现
set
hashSet:
treeSet:
map:
hashMap:
treeMap:
currentHshMap:
知识点：
哈希表：
解决hash冲突的方法：线性探测法和拉链法，hashmap和redis中的hash表都是用拉链法解决哈希冲突的
二叉树：
红黑树：
currenthashmap的实现及应用：