常用数据结构
Java中常用的数据结构主要分为Collection和Map接口。Collection下分为List（列表）和Set（保证集合中元素唯一）两个接口。ArrayList和Vector分别实现List，基于数组的数据结构，两者主要区别在于线程安全问题。LinkedList也实现List接口，基于双向链表结构实现。数组：查询快、增删数据需要移动数据，若支对单条数据插入或删除，ArrayList的速度反而优于LikedList,批量随机增删数据，LikedList更占优势。
实现Set接口有HashSet和TreeSet：
元素唯一。HashSet没有实现排序，顺序有可能发生变化；存入的值可以为null，但只能有一个；线程不同步。
当一个对象存入HashSet中，首先通过比较hashcode值，然后根据该值确定内存存放位置。存放的对象重写equal方法和hashCode方法，规则是如果两个对 象通过equals方法比较返回true时，其hashCode也应该相同
TreeSet是SortedSet唯一实现类。内部通过二叉树实现排序，不允许放入null值。TreeSet分为自然排序和定制排序。
自然排序：使用要排序元素的CompareTo方法（Comparable接口中的方法），默认是升序排序。
定制排序：实现Comparetor接口的compare(T o1,To2);
HashMap通过hashCode对其内容进行查询，在Map 中插入、删除和定位元素，HashMap是最好的选择。。如果想按照自然顺序或自定义谁许遍历键，那么TreeMap更好
HashTable与HashMap
- 同步性:Hashtable是线程安全的，也就是说是同步的，而HashMap是线程序不安全的，不是同步的。
- HashMap允许存在一个为null的key，多个为null的value 。
- hashtable的key和value都不允许为null。
并发集合了解哪些？
ArrayBlockingQueue
LinkedBlockingQueue
ConcurrentLinkedQueue
ConcurrentHashMap:HashTable容器使用synchronized来保证线程安全，在线程竞争激烈的情况下HashTable的效率非常低下。
ConcurrentHashMap采用了Segment分段技术，容器里有多把锁，每把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率。
CopyOnWriteArrayList
AbstractQueuedSynchronizer
ThreadPoolExecutor
集合类以及集合框架
HashMap
探究HashMap之前，我们需要知道什么是哈希表（又称散列表）
- 数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组逐一对比，时间复杂度为O(n)，当然对于有序数组，可以采用二分查找，插值查找，斐波那契查找等方式，复杂度提过为O(logn)；对于增删操作，涉及到数组元素的移动，器评价复杂度为O(n)；
- 线性链表：对于增删操作，在找到指定操作位置后，仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表，复杂度为O(n)；
- 二叉树：对一颗相对平衡有序的二叉树，增删查平均复杂度为O(logn)
- 哈希表：相比较以上三种结构，哈希表中增删查性能十分之高，不考虑哈希碰撞，时间复杂度为O(1)。其实数据结构物理存储结构只有两种：顺序存储结构和链表，像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中也是这两种物理组织形式。哈希表的主干就是数组，可根据下标快速查找，如果是赠删查某个元素，通过元素的关键字，映射到数组中某个位置，一次就能定位完成操作。
- 哈希冲突：通过哈希函数计算的实际存储地址可能别其他的某个元素已经占用，这种情况就称为哈希冲突（哈希碰撞）。哈希函数的设计至关重要，它应尽可能的保证计算简单并且散列地址分布均匀，但是数组是一块连续的固定长度的空间，再好的哈希函数也不能保证不发生冲突，入到冲突有多种方法：开发定址法（寻找下一块未使用的地址），在散列函数法，链地址法，HashMap采用第三种，也就是数组+链表的形式。
1.HashMap的实现原理
HashMap的主干是一个Entry数组，Entry:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，急需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
2.HashMap数据结构
3.HashMap源码理解
4.HashMap如何put数据（从HashMap源码角度讲解）
public V put(K key, V value) {
// 如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），
// 入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
int i = indexFor(hash, table.length);//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
// 如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
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;
}
}
modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i);//新增一个entry
return null;
}
private void inflateTable(int toSize) {
int capacity = roundUpToPowerOf2(toSize);
// capacity一定是2的次幂
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 此处为threshold赋值，取capacity*loadFactor
// 和MAXIMUM_CAPACITY+1的最小值，
// capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
hash函数
//这是一个神奇的函数，用了很多的异或，移位等运算，
//对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
以上hash函数计算出的值，通过indexFor进一步处理来获取实际的存储位置
/**
* 返回数组下标
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
再来看看addEntry的实现：
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
通过以上代码能够得知，当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
5.HashMap get();
public V get(Object key) {
//如果key为null,则直接去table[0]处去检索即可。
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//通过key的hashcode值计算hash值
int hash = (key == null) ? 0 : hash(key);
// indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，
// 通过equals方法比对找出对应记录
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 != null && key.equals(k))))
return e;
}
return null;
}
可以看出，get方法的实现相对简单，key(hashcode)-->hash-->indexFor-->最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null。
网友评论