一只不甘沦为码农的程序猿

Java集合框架

2019-03-24  本文已影响0人  zorkelvll
image

ZERO

    持续更新 请关注：https://zorkelvll.cn/blogs/zorkelvll/articles/2018/12/16/1544926812927

背景

    本文主要是记录在学习 Java集合框架过程中的一些知识点备忘！

20181218

1、List VS Set VS Map

2、Arraylist VS LinkedList

Arraylist底层使用的是数组（=>存储、读取效率高，插入删除特定位置效率低【时间复杂度浸塑为O（n）】）；LinkedList底层使用的是双向循环链表数据结构（插入删除特定位置侠侣特别高【时间复杂度近似为O（1）】）

3、Arraylist VS Vector

Vector类所有方法均是同步的，多个线程可以安全地访问一个Vector对象，但是相比较而言的一个线程访问Vector时程序代码需要在同步操作室耗费大量的时间；而Arraylist不是同步的！

20181217

1、HashMap为什么是线程不安全的？

在多线程下，进行put操作可能会导致HashMap死循环问题，原因在于HashMap的扩容resize()方法；

这是由于扩容是新建一个数组，复制原数据到数组；又由于数组下标挂有链表，因此也需要复制链表，但是多线程操作可能导致出现环形链表，例如：

若2个线程同时扩容，比如线程1先将A复制到新的hash表中，然后接着复制B到链头,本来B.next = null到此也就结束了（跟线程2过程一样）；但是，由于线程2扩容的原因，将B.next = A,继续复制A，让A.next=B,由此出现B.next=A;A.next=B

（线程2：将0-A->B->NULL =》0-B->A->NULL，则线程1：0->B->A->B）

=》JDK1.8中已经解决了死循环问题(在resize方法中，声明两个引用地址，维护两个链表，依次在末端添加新元素，在多线程操作情况下，无非是第二个线程重复第一个线程一模一样的操作而已)，虽然多线程put操作不会导致死循环问题，但依然有其他的弊端如数据丢失等问题，因此多线程情况下还是应该使用ConcurrentHashMap

2、HashMap VS HashSet

HashSet底层是基于HashMap实现的，HashSet中的方法除了clone\writeObject\readObject方法外，其他方法都是直接调用HashMap中的方法的

3、ConcurrentHashMap VS Hashtable

二者的区别主要体现于线程安全的实现方式上不同

4、ConcurrentHashMap线程安全的具体实现方式/底层实现原理

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成；Segment实现了ReentrantLock,是一种可重入锁，扮演锁的角色；HashEntry用于存储键值对数据

一个ConcurrentHashMap中包含一个Segment数组，Segment的结构与HashMap类似，是一种数组和链表结构，一个Segment包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得对应的Segment的锁

synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍

5、集合框架底层数据结构总结

List:

(1)Arraylist:Object数组
(2)Vector:Object数组
(3)LinkedList:双向链表（JDK1.6之前为循环链表，JDK1.7取消了循环）

Set:

(1)HashSet（无序，唯一）：基于HashMap实现，底层采用HashMap来保存元素
(2)LinkedHashSet:继承于HashSet，且其内部是通过LinkedHashMap实现的
(3)TreeSet(有序，唯一)：红黑树（自平衡的排序二叉树）

20181216

1、ArrayList VS LinkedList

=>

=>

=>

2、ArrayList VS Vector

3、HashMap的底层实现

底层是“数组+链表”数据结构，即链表散列；

HashMap通过key的hashCode经过扰动函数处理过后得到hash值，然后通过(n-1)&hash判断当前元素存放的位置（n即数组的长度），如果当前位置存在元素的话则判断该元素与要存入的h元素的ash值以及key是否相同，如果相同的话则直接覆盖，否则不相同则通过拉链法解决冲突

扰动函数：也就是HashMap的hash方法，该方法即扰动函数主要是为了防止一些实现比较差的hashCode方法，以减少碰撞

hash方法源码：

//jdk1.8方法相较于jdk1.7更加简化，但是原理不变
static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//jdk1.7，该方法性能会稍差一点点，因为毕竟扰动了4次
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

拉链法：将链表和数组相结合，即创建一个链表数组，数组中每一格都是一个链表，若遇到hash冲突则将冲突的值加到链表中即可

在JDK1.8中，对于解决哈希冲突有了较大的变化，当链表长度大于阈值（默认8），则会将链表转化为红黑树，以减少搜索时间

TreeMap、TreeSet以及JDK1.8之后的HashMap底层均用到红黑树，红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构

4、HashMap VS HashTable

5、HashMap的长度为什么是2的幂次方

为了能够让HashMap存取高效，尽量减少碰撞，也即要尽量把数据分配均匀！Hash值范围是-2147483648~2147483648，共约40亿映射空间，只要hash函数映射的比较均匀松散，一般很难出现碰撞，但是40亿长度的数组在内存中存放不下的，因此这个散列值是不能直接使用的

=>考虑先对数组的长度进行取模运算，计算的余数用来作为存放的位置也即数组下标，即数组下标的计算方法是“(n-1) & hash”，其中n为数组长度,这也就是为什么HashMap的长度是2的幂次方

=>为什么是2的幂次方？：：取模运算，首先就是采用%操作进行实现，=>"取余%操作中，在除数是2的幂次方时，等价于与其除数减一的与&操作，也即hash%length == hash&(length-1),,这个等价的前提就是length是2的n次方"

=>并且，在采用二进制位操作&，相对于%能够提高运算效率，这也是为什么HashMap的长度要是2的幂次方！

说明：本JavaGuide系列博客为来源于https://github.com/Snailclimb/JavaGuide
等学习网站或项目中的知识点，均为自己手打键盘系列且内容会根据继续学习情况而不断地调整和完善！

上一篇 下一篇

猜你喜欢

热点阅读