3483°

HashMap,HashTable解析

  • HashMap;
大家之前都了解HashMap,但是大家都知道HashMap 是数组+TreeNode结构,也很了解,为什么在HashMap如此快,其实在HashMap过程中,对数据集合做了Hash ,其实让数据分片于不同的“桶”中。
其实对于HashMap的插入的最高境界是减少Hash碰撞;
在源码处理过程中,针对HashMap的开始也初始化了几个大家看到源码的时候,也能见到;
几个值:
  1. 默认容量;--》 16 (测试最后也是建议2的N次幂,jdk的默认是16,在阿里的开发规范中也是建议设置这个值,当然也必须是2的N次幂,在未知大小的情况下建议使用JDK的默认 1<<4 16值)
  2. 最大容量--》这个也是2 的30 次幂
  3. 加载因子:0.75 (也就是在当默认桶容量的值中*加载因子的时候,会让桶扩容)。
  4. treenode 的容量,其实也就是桶中的数据量大小设置也就是值大于这个值得时候,将某桶的数据由链表转换为红黑树结构。(这个好像是jdk8以后的功能。)
这几个也是主要的值。
/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 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; /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */ static final int TREEIFY_THRESHOLD = 8; /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */ static final int MIN_TREEIFY_CAPACITY = 64;
  1. 为什么HashMap是线程不安全的,实际会如何体现?
    1. 第一,如果多个线程同时使用put方法添加元素
      1. 假设正好存在两个put的key发生了碰撞(hash值一样),那么根据HashMap的实现,这两个key会添加到数组的同一个位置,这样最终就会发生其中一个线程的put的数据被覆盖。
    2. 第二,如果多个线程同时检测到元素个数超过数组大小*loadFactory
      1. 这样会发生多个线程同时对hash数组进行扩容,都在重新计算元素位置以及复制数据,但是最终只有一个线程扩容后的数组会赋给table,也就是说其他线程的都会丢失,并且各自线程put的数据也丢失。且会引起死循环的错误。
  • HashTable
    • 根据数据特性,刚也解释过HashMap的线程不安全,为了解决HashMap的数据不安全。
      • 通过Collections.synchronizeMap(hashMap);
      • 直接使用Hashtable,但是当一个线程访问HashTable的同步方法时,其他线程如果也要访问同步方法,会被阻塞住。举个例子,当一个线程使用put方法时,另一个线程不但不可以使用put方法,连get方法都不可以,效率很低,现在基本不会选择它了。
      • 直接使用JDK 5 之后的 ConcurrentHashMap,如果使用Java 5或以上的话,请使用ConcurrentHashMap。(下期解释ConCUrrentHashMap)
    • 这期我们来解释HashTable;
      • 底层数组+链表实现,无论key还是value都不能为null,线程安全,实现线程安全的方式是在修改数据时锁住整个HashTable,效率低,ConcurrentHashMap做了相关优化
        • 在业务方法中将方法做了同步处理。
/** * Copies all of the mappings from the specified map to this hashtable. * These mappings will replace any mappings that this hashtable had for any * of the keys currently in the specified map. * * @param t mappings to be stored in this map * @throws NullPointerException if the specified map is null * @since 1.2 */ public synchronized void putAll(Map<? extends K, ? extends V> t) { for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) put(e.getKey(), e.getValue()); }
      • 初始size为11,扩容:newsize = olesize*2+1
      • 计算index的方法:index = (hash & 0x7FFFFFFF) % tab.length
/** * Constructs a new, empty hashtable with a default initial capacity (11) * and load factor (0.75). */ public Hashtable() { this(11, 0.75f); } /** * Constructs a new hashtable with the same mappings as the given * Map. The hashtable is created with an initial capacity sufficient to * hold the mappings in the given Map and a default load factor (0.75). * * @param t the map whose mappings are to be placed in this map. * @throws NullPointerException if the specified map is null. * @since 1.2 */ public Hashtable(Map<? extends K, ? extends V> t) { this(Math.max(2*t.size(), 11), 0.75f); putAll(t); }
从这行代码中也可以证明上述的逻辑。
 


全部评论: 0

    我有话说: