- 常用数据结构简介
数据元素相互之间的关系称为结构。
有四类基本结构：集合、线性结构、树形结构、图状结构。
1，集合结构：除了同属于一种类型外，别无其它关系。
2，线性结构：元素之间存在一对一关系常见类型有:?数组,链表,队列,栈,它们之间在操作上有所区别。
例如：链表可在任意位置插入或删除元素,而队列在队尾插入元素,队头删除元素, 栈只能在栈顶进行插入,删除操作.
3，树形结构：元素之间存在一对多关系,常见类型有:树(有许多特例:二叉树、平衡二叉树、查找树等)。
4，图形结构：元素之间存在多对多关系,图形结构中每个结点的前驱结点数和后续结点多个数可以任意。 - 并发集合了解哪些？
竟一个都没用过
并发集合类 - 列举java的集合以及集合之间的继承关系
继承关系
java集合继承关系及特点 -
集合类以及集合框架
完整集合框架
- 容器类介绍以及之间的区别（
容器类估计很多人没听这个词，Java容器主要可以划分为4个部分：List列表、Set集合、Map映射、工具类（Iterator迭代器、Enumeration枚举类、Arrays和Collections），具体的可以看看这篇博文 Java容器类） - List,Set,Map的区别
详见上边各帖 - List和Map的实现方式以及存储方式
详见上边各贴 - HashMap的实现原理
HashMap的实现原理
HashMap实现原理及源码分析 - HashMap数据结构？
见上 - HashMap源码理解
见上 - HashMap如何put数据（从HashMap源码角度讲解）？
//存储
public V put(K key, V value) {
// HashMap允许存放null键和null值。
// 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。
if (key == null)
return putForNullKey(value);
// 根据key的keyCode重新计算hash值。
int hash = hash(key.hashCode());
// 搜索指定hash值在对应table中的索引。
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果i索引处的Entry为null，表明此处还没有Entry。
modCount++;
// 将key、value添加到i索引处。
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
// 获取指定 bucketIndex 索引处的 Entry
Entry<K,V> e = table[bucketIndex];
// 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// 如果 Map 中的 key-value 对的数量超过了极限
if (size++ >= threshold)
// 把 table 对象的长度扩充到原来的2倍。
resize(2 * table.length);
}
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1);
}
//获取
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
简单来说就是将Entry根据hash算法放入数组的链表中的一个过程
详见上
- HashMap怎么手写实现？
见上 - ConcurrentHashMap的实现原理
Java并发包中提供的一个线程安全且高效的HashMap实现，策略就是分段锁机制。
ConcurrentHashMap实现原理及源码分析 - ArrayMap和HashMap的对比
ArrayMap和HashMap区别 - HashTable实现原理
HashTable的使用和原理 - TreeMap具体实现
TreeMap - HashMap和HashTable的区别
（1）基类不同：HashTable基于Dictionary类，而HashMap是基于AbstractMap。Dictionary是什么？它是任何可将键映射到相应值的类的抽象父类，而AbstractMap是基于Map接口的骨干实现，它以最大限度地减少实现此接口所需的工作。
（2）null不同：HashMap可以允许存在一个为null的key和任意个为null的value，但是HashTable中的key和value都不允许为null。
（3）线程安全：HashMap时单线程安全的，Hashtable是多线程安全的。
（4）遍历不同：HashMap仅支持Iterator的遍历方式，Hashtable支持Iterator和Enumeration两种遍历方式 - HashMap与HashSet的区别
两者区别
HashMap和HashSet的区别 - 集合Set实现Hash怎么防止碰撞
Java集合---HashSet的源码分析 - ArrayList和LinkedList的区别，以及应用场景
1,如果应用程序对各个索引位置的元素进行大量的存取或删除操作，ArrayList对象要远优于LinkedList对象；
2,如果应用程序主要是对列表进行循环，并且循环时候进行插入或者删除操作，LinkedList对象要远优于ArrayList对象；
ArrayList和LinkedList区别及使用场景 - 数组和链表的区别
数组 分配内存连续，长度固定，插入，删除操作效率低
链表 分配内存不连续，长度不固定，插入，删除操作效率高 - 二叉树的深度优先遍历和广度优先遍历的具体实现
public void depthFirst() {
Stack<Map<String, Object>> nodeStack = new Stack<Map<String, Object>>();
Map<String, Object> node = new HashMap<String, Object>();
nodeStack.add(node);
while (!nodeStack.isEmpty()) {
node = nodeStack.pop();
System.out.println(node);
//获得节点的子节点，对于二叉树就是获得节点的左子结点和右子节点
List<Map<String, Object>> children = getChildren(node);
if (children != null && !children.isEmpty()) {
for (Map child : children) {
nodeStack.push(child);
}
}
}
}
//节点使用Map存放
public void breadthFirst() {
Deque<Map<String, Object>> nodeDeque = new ArrayDeque<Map<String, Object>>();
Map<String, Object> node = new HashMap<String, Object>();
nodeDeque.add(node);
while (!nodeDeque.isEmpty()) {
node = nodeDeque.peekFirst();
System.out.println(node);
//获得节点的子节点，对于二叉树就是获得节点的左子结点和右子节点
List<Map<String, Object>> children = getChildren(node);
if (children != null && !children.isEmpty()) {
for (Map child : children) {
nodeDeque.add(child);
}
}
}
}
//这里使用的是双端队列，和使用queue是一样的
-
堆的结构
特殊的一种树
基本数据结构――堆的基本概念及其操作
彻底弄懂最大堆的四种操作(图解+程序)（JAVA） -
堆和树的区别
二叉排序树与堆的区别 -
堆和栈在内存中的区别是什么(解答提示：可以从数据结构方面以及实际实现方面两个方面去回答)？
堆和栈的区别（内存和数据结构） -
什么是深拷贝和浅拷贝
直接赋值：两变量指向同一对象，对任一变量操作发生变化，两变量均改变。
浅拷贝：创建一个新对象，然后将当前对象的非静态字段复制到该新对象，如果字段是值类型的，那么对该字段执行复制；如果该字段是引用类型的话，则复制引用但不复制引用的对象。因此，原始对象及其副本引用同一个对象。（String是引用类型，但是有值类型特性）
深拷贝：创建一个新对象，然后将当前对象的非静态字段复制到该新对象，无论该字段是值类型的还是引用类型，都进行复制。（在浅拷贝的基础上，每次拷贝将引用类型创建新对象）
一看就懂的，java深拷贝浅拷贝 -
手写链表逆序代码
单链表反转java代码 -
讲一下对树，B+树的理解
讲一下对树，B+树的理解 -
讲一下对图的理解
浅析数据结构-图的基本概念 -
判断单链表成环与否？
判断单链表成环与否 -
合并多个单有序链表（假设都是递增的）
合并k个有序的链表
问题来自：AWeiLoveAndroid的博客
网友评论