JDK源码之HashMap

什么是HashMap

HashMap是一个可以提供O(1)时间复杂度的数据结构,由数组和链表数据结构组成。在对存入的key进行hash之后,然后用hash值在数组上确定一个位置,把value对象以Node节点形式放入到数组的链表当中。

jdk1.8之后对此做了优化,因为如果发生了数据倾斜,可能会使数组某个下标的Node链表非常长,因为链表查询起来比较慢,所以1.8之后修改了,当Node链表长度大于8时,会把该下标位置的链表数据结构修改为红黑树的结构来保证查询的速度。当数据长度小于8时,会再修改为链表。

使用场景

个人理解使用场景应该是在不需要复杂的查询,只需要一个Key对应一个Value,写入少的场景。因为像HashMap,ArrayList这种数据结构都提供了自动扩容的功能,像HashMap的负载因子是0.75,也就是当数组中75%的位置都有值以后会进行扩容。每次扩容的时候都涉及到每个数据的rehash和数组的复制,所以当写入数据量非常大的时候,会不断的进行rehash和复制,有可能会造成CPU占用率非常高(这只是个人平时学习的理解,如果有不对之处请大家指正)。

所以个人感觉HashMap的使用场景也是读多写少的场景,可以提供很快速度的读,写入的速度也可以,但如果提前知道Map里要放入多少数据,最好在new对象的时候,就手动指定出长度,这样可以避免rehash,从来变相提高使用效率。

源码实现 jdk1.8版本

以下的代码都是代码在上面,解释在下面。

变量声明
1
2
3
4
	 /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

这个值是HashMap默认初始化的长度,也就是16长。

1
2
3
4
5
6
	/**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30; //1073741824

这里按注释看,应该是HashMap支持的最大长度,如果超过这个值,则使用这个值。

JDK源码之CopyOnWriteArrayList

什么是CopyOnWriteArrayList

CopyOnWriteArrayList是一个线程安全的List,和它相同的还有这几个,Vectory,SynchronizedList。 它们都是实现了List接口的线程安全类。

CopyOnWriteArrayList使用的是一种写时复制的算法,也就是说在执行add方法的时候,并不像传统的ArrayList一样在当前数组直接操作, 而是在执行add方法的时候,会把原来的数组复制并且长度+1,然后把新值设置到新的数组中,然后把新数组设置为当前使用状态,由于数组是volatile修饰的,所以JVM会自动来保证数组的可见性。

这样使此List在读取时可以不用加锁,提高读取效率,但是在添加的时候效率会很低下。所以我感觉CopyOnWriteArrayList的使用场景就是读多写少的场景,甚至在尽可能的情况下,不去写。这样才能发挥此数据结构的最大优点。

hexo next主题添加LeanCloud统计功能

遇到的问题 网上能查到很多next主题添加LeanCloud主题的方法,但我看都是说在站点的_config.yml中添加 1 2 3 4 leancloud_visitors: enable: true app_id: appid app_key: key