inheritance

  • Collection
    • List—允许有重复，它对集合中的对象进行索引
      • Vector
        • synchronizes on each individual operation
        • obsolete
      • LinkedList
        • 链表
        • 新增和删除操作add和remove，效率高
        • 查询操作性能比较低
      • ArrayList
        • 数组
        • 因为地址连续， ArrayList要移动数据,所以插入和删除操作效率比较低
    • Set—不允许对象有重复的值
      • HashSet，使用hash表存储元素，元素无序且唯一，遍历输出顺序不一定和插入的顺序一致
        • LinkedHashSet，内部用了Double linked list记录顺序，输出结果顺序和插入顺序一致
      • TreeSet，使用二叉树[红黑树]实现，元素唯一，而且根据值排序
  • Collection
    • Map
      • TreeMap
        • 基于红黑树对所有key进行排序
      • HashMap
        • LinkedHashMap，迭代时输出结果和插入顺序一致
      • IdentifyHashMap
        • IdentityHashMap使用 == 判断两个key是否相等，而HashMap使用的是equals方法比较key值

HashMap

HashMap详解

how it work

  • HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。
  • 当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。
    • HashMap是在bucket中储存键对象和值对象，作为Map.Entry
  • 当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。
  • HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中

HashMap的数据结构为数组 + 链表

  • 计算位置方法：tab[i = (n - 1) & hash]
  • JDK8优化，当链表超过8时，链表就转换为红黑树
  • HashMap vs HashTable—HashMap几乎可以等价于Hashtable
    • HashTable key 和value都不允许为null
      • HashMap key和value都允许为null：key只能有一个为null，而value则可以有多个为null
    • 线程安全
      • HashMap是非synchronized的
      • HashTable是synchronized，速度可能会慢
    • 位置索引方法
      • HashTable-%运算
      • HashMap-&运算
    • CocurrentHashMap比HashTable更加好
      • 同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁
  • HashMap优化：自定义数组容量和加载因子，HashMap(int initialCapacity, float loadFactor)
    • 初始容量默认为16,负载因子(loadFactor)默认是0.75; map扩容后，要重新计算阈值
    • 当元素个数 大于新的阈值时，map再自动扩容；以默认值为例，阈值=16*0.75=12，当元素个数大于12时就要扩容
    • loadFactor过大时，map内的数组使用率高了，内部极有可能形成Entry链，影响查找速度
    • loadFactor过小时，map内的数组使用率较低低，占用更多的内存

Collections.synchronizedMap vs HashTable

  • 都是简单粗暴的通过synchronized来保证线程安全
  • api上面大同小异
    • HashTable会多一些api（map interface + enhanced interface）
    • synchronizedMap遵循map interface
  • 锁
    • HashTable都是在方法加锁
    • Collections.synchronizedMap(Map)内部会有object mutex变量，synchronized + mutex 细粒度
  • HashTable尽管性能不如ConcurrentHashmap,但是不能完全被取代
    • hashtable是强一致性—操作是阻塞的
    • ConcurrentHashMap是弱一致性—设计是非阻塞

重写equals的时候必须要重写hashcode

  • 保证通过equal判断相等的两个对象，调用hashcode方法也需要返回同样的整数值
    • equal方法判断不同两个对象，hashcode可能相同[hash冲突]
    • 重写hashcode，保证语义上相等的对象，hashcode是一样的
  1. HashMap<Person,String> map = new HashMap<Person, String>();
  2. Person person = new Person(1234,"乔峰");
  3. //put到hashmap中去
  4. map.put(person,"天龙八部");
  5. //get取出，从逻辑上讲应该能输出“天龙八部”, 但是实际结果输出为null
  6. System.out.println("结果:"+map.get(new Person(1234,"萧峰")));

为什么String， Interger这样的wrapper类适合做为key

  • 因为获取对象的时候要用到equals()和hashCode()方法
  • 如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能

HashTable和ConcurrentHashMap不允许key和value为null

  • HashTable和ConcurrentHashMap都要考虑线程安全
  • 如果允许的话, HT和CHM使用map.get(key)是返回null无法判断key是不存在还是值为空
    • 普通HashMap还可以通过map.contains(key)来检查
    • HT和CHM因为线程安全问题，因为线程调度，两次调用间已经发生了改变

Collections Thread Safe

大体分为两类：synchronized Collections 和 concurrent Collections

synchronized Collections vs concurrent Collections

其实都是粒度问题

  • synchronized Collections 基本都是简单使用synchronized，性能偏低
    • entire collection are locked
  • Concurrent Collections 会有更加优化方案，更细粒度
    • ConcurrentHashMap

synchronizedCollection(Collection c)

  • 使用一个wrapper类: SynchronizedCollection implements Collection, Serializable
    • 里面的add, addAll等方法都使用synchronized加锁
  1.     val syncColleciton = Collections.synchronizedCollection(ArrayList<Int>())
  2.     val thread1 = thread {
  3.         syncColleciton.addAll(listOf(1, 2, 3, 4, 5, 6))
  4.     }
  5.     val thread2 = thread {
  6.         syncColleciton.addAll(listOf(1, 2, 3, 4, 5, 6))
  7.     }
  8.     thread1.join()
  9.     thread2.join()
  10.     //如果不使用线程安全的类，有时候是12 有时候不是
  11.     assert(syncColleciton.size == 12)
  • 和上面的synchronizedCollection类似，都是返回一个wrapper对象，使用synchronized保证线程安全
  1.         val syncList = Collections.synchronizedList(ArrayList<Int>())
  2.         val syncMap = Collections.synchronizedMap(HashMap<String, String>())
  3.         val syncSortedMap = Collections.synchronizedSortedMap(TreeMap<String, String>())
  4.         val syncSet = Collections.synchronizedSet(HashSet<String>())

concurren collections

  • ConcurrentHashMap
    • 数组+链表, Segment—-jdk 1.7
      • Segment[]数组来将Hash表实现分段存储，从而实现分段加锁
      • Segment继承了ReetrantLock，表示Segment是一个可重入锁
      • 每个Segment元素，即每个分段则类似于一个Hashtable
    • 数组+链表+红黑树, CAS + Synchronized—JDK 1.8
      • put操作，先判断bucket，tabAt(tab, i = (n - 1) & hash)==null
        • bucket为null的时候，采用CAS操作，如果CAS操作失败说明多线程写，别的线程抢先写了，也就是hash冲突
        • bucket不为null的时候，使用锁，synchronized更新或者插入节点
        • 使用CAS 增加baseCount， 失败则把当值放进counters数组
      • tabAt函数调用，采用Unsafe.getObjectVolatie()来获取，而不是直接用table[index]
        • Volatile access methods
      • size方法，元素总数 = baseCount + sum(CounterCell)
  • BlockingQueue