Fluge Site

从HashMap并发的死循环可以知道,Hashmap是没办法在多线程的情况下使用的，为了解决这个问题，在Java4之前用的是hashtable,只是现在不推荐的。在Java5之后就比较推荐使用java.util.concurrent.ConcurrentHashMap，这个在多线程的情况下，也能有很好的性能。从这里引入了Java里面一类很重要的概念—并发。先解决完上一个问题。高并发下ConcurrentHashMap的结构。

并发的一些初步了解–synchronized和volatile

在多线程的并发的情况下有安全的访问变量，为了解决这个问题引入一个机制—锁机制。让多线程不能同时访问一个共享变量。在并发过程中有需要简单的了解两个东西的含义。

Java中的synchronized的简单分析

synchronized的用法要弄清晰一个问题:synchronized锁住的是代码还是对象？
首先是一个被synchronized修饰的代码块

HashMap从设计上来说就不适合在并发的情况的下使用,因为HashMap每次在put()时，总会检查一遍对应桶的容量，如果桶满了，或者超过了设定的值，就会reserve()来进行扩容,然后通过get()来取出相应的值。这个过程在单线程下是没什么问题的，但是如果在并发的条件下，多个线程同时reserve桶，然后有线程这个时候执行get()就有可能产生死循环，造成CPU的100%占用，具体等会看源码。在Java里面有一个很老的hashtable就是加了锁的HashMap。现在Java中多线程里一般使用ConcurrentHashMap，至于为什么。会在下一篇博文里分析。

HashMap的rehash源代码

put()方法的Java8源码分析看我的Java里的hashMap和golang里的map，在Java8中优化了扩容的hash算法，更加高效。在这分析死循环用的是Java7的源码。更加清晰点。

哈希表

哈希表就是一种以键-值(key-value)存储数据的结构,我们只要输入待查找的键即Key,即可找到对应的值。
使用哈希找查有两个步骤:

1. 使用哈希函数将被找查的键转换为数组的索引.在理想的情况下,不同的键会被装换为不同的索引值,但是在有些情况下我们需要处理多个键被哈希到同一个索引值得情况。所以哈希查找的第二个步骤是处理冲突。
2. 处理哈希碰撞冲突。一般处理哈希碰撞用拉链法和开放寻址法等方法。

   开放地址法:当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。
   拉链法:当通过哈希函数把键转换为数组的索引时,如果索引重复,就在该位置用链表顺序 存储该键值对。

Java中的HashMap

基本认识：基于Map接口,允许null键/值,非同步,不保证有序,也不保证顺序不随时间变化。
HashMap中和Map一样，键值对都是保存在一个内部类中的,而在HashMap类中有一个很重要的字段，那就是Node[] table，即是一个哈希桶数组。Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。

1
2
3
4
5
6
7
8
9

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node

        Node(int hash, K key, V value, Node<K,V> next) { ... }
       /.../
}

Java里的动态数组—ArrayList

ArrayList是实现List接口的动态数组，每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。随着向ArrayList中不断添加元素，容量会自动增长，自动增长会带来数据向新数组的重新拷贝。同时需要注意的是这个实现不是同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。(结构上的修改是指任何添加或删除一个或多个元素的的操作，或者显示调整底层数组的大小；仅仅设置元素的值不是结构上的修改)