Java温故而知新（1）

Java中的集合类有以下所属关系：Hash算法HashMap使用Hash算法，所以在解剖HashMap之间，需要先简单的了解Hash算法，Hash算法一般也成为散列算法，通过散列算法将任意的值转化成固定的长度输出，该输出就是散列值，这是一种压缩映射，也就是，散列值的空间远远小于输入的值空间。下面我们建立一个HashMap,然后往里面放入12对key-value，这个HashMap的默认数组长度为16，我们的key分别存放在该数组的格子中，每个格子下面存放的元素又是以链表的方式存放元素。

  public static void main(String[] args) {    Map map = new HashMap();    map.put("What", "chenyz");    map.put("You", "chenyz");    map.put("Don't", "chenyz");    map.put("Know", "chenyz");    map.put("About", "chenyz");    map.put("Geo", "chenyz");    map.put("APIs", "chenyz");    map.put("Can't", "chenyz");    map.put("Hurt", "chenyz");    map.put("you", "chenyz");    map.put("google", "chenyz");    map.put("map", "chenyz");    map.put("hello", "chenyz");  }

当我们新添加一个元素时，首先我们通过Hash算法计算出这个元素的Hash值的hashcode，通过这个hashcode的值，我们就可以计算出这个新元素应该存放在这个hash表的哪个格子里面，如果这个格子中已经存在元素，那么就把新的元素加入到已经存在格子元素的链表中。运行上面的程序，我们对HashMap源码进行一点修改，打印出每个key对象的hash值What-->hash值：8计算出来的Hash值分别代表该key应该存放在Hash表中对应数字的格子中，如果该格子已经有元素存在，那么该key就以链表的方式依次放入格子中从上表可以看出，Hash表是线性表和链表的综合所得，根据数据结构的定义，可以得出粗劣的结论，Hash算法的存取速度要比数组差一些，但是比起单纯的链表，在查找和存取方面却要好多。如果要查找一个元素时，同样的方式，通过Hash函数计算出这个元素的Hash值hashcode，然后通过这个hashcode值，直接找到跟这个hash值相对应的线性格子，进如该格子后，对这个格子存放的链表元素逐个进行比较，直到找到对应的hash值。在简单了解完Hash算法后，我们打开HashMap源码初始化HashMap下面我们看看Map map = new HashMap();这段代码究竟做了什么，发生了什么数据结构的变化。HashMap中几个重要的属性transient Entry[] table;transient int size;final float loadFactor;int threshold;

public class HashMap<K,V>  extends AbstractMap<K,V>  implements Map<K,V>, Cloneable, Serializable{  int threshold;    final float loadFactor;  transient Entry[] table;  static final float DEFAULT_LOAD_FACTOR = 0.75f;  static final int DEFAULT_INITIAL_CAPACITY = 16;  public HashMap(int initialCapacity, float loadFactor) {    if (initialCapacity < 0)      throw new IllegalArgumentException("Illegal initial capacity: " +                        initialCapacity);    if (initialCapacity > MAXIMUM_CAPACITY)      initialCapacity = MAXIMUM_CAPACITY;    if (loadFactor <= 0 || Float.isNaN(loadFactor))      throw new IllegalArgumentException("Illegal load factor: " +                        loadFactor);    // Find a power of 2 >= initialCapacity    int capacity = 1;    while (capacity < initialCapacity)      capacity <<= 1;    this.loadFactor = loadFactor;    threshold = (int)(capacity * loadFactor);    table = new Entry[capacity];    init();  }

首先是要确定hashMap的初始化的长度，这里使用的策略是循环查出一个大于initialCapacity的2的次方的数，例如initialCapacity的值是10，那么大于10的数是2的4次方，也就是16，capacity的值被赋予了16，那么实际上table数组的长度是16，之所以采用这样的策略来构建Hash表的长度，是因为2的次方运算对于计算机来说是有相当的效率。loadFactor，被称为负载因子，HashMap的默认负载因子是0.75fthreshold，接下来是重构因子，由负载因子和容量的乘机组成，它表示当HashMap元素被存放了多少个之后，需要对HashMap进行重构。通过这一系列的计算和定义后，初始化Entry[] table;put(key,value)接下来看一对key-value是如何被存放到HashMap中：put(key,value) 

  public V put(K key, V value) {    if (key == null)      return putForNullKey(value);    int hash = hash(key.hashCode());        int i = indexFor(hash, table.length);    System.out.println(key+"-->hash值："+i);//这就是刚才程序打印出来的key对应hash值    for (Entry<K,V> e = table[i]; e != null; e = e.next) {      Object k;      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {        V oldValue = e.value;        e.value = value;        e.recordAccess(this);        return oldValue;      }    }    modCount++;    addEntry(hash, key, value, i);    return null;  }  static int hash(int h) {    h ^= (h >>> 20) ^ (h >>> 12);    return h ^ (h >>> 7) ^ (h >>> 4);  }  static int indexFor(int h, int length) {    return h & (length-1);  }

这里是整个hash的关键，请打开源码查看一步一步查看。hash(key.hashCode()) 计算出key的hash码 //对于hash()的算法，这里有一篇分析很透彻的文章<HashMap hash方法分析>

  void addEntry(int hash, K key, V value, int bucketIndex) {    Entry<K,V> e = table[bucketIndex];    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);    if (size++ >= threshold)      resize(2 * table.length);  }

Entry<K,V> e = table[bucketIndex];  创建一个Entry对象来存放键值（ps:Entry对象是一个链表对象）

  void resize(int newCapacity) {    Entry[] oldTable = table;    int oldCapacity = oldTable.length;    if (oldCapacity == MAXIMUM_CAPACITY) {      threshold = Integer.MAX_VALUE;      return;    }    Entry[] newTable = new Entry[newCapacity];    transfer(newTable);    table = newTable;    threshold = (int)(newCapacity * loadFactor);  }

这里为什么是否需要扩容重构，其实是涉及到负载因子的性能问题loadFactor负载因子get(key)接下来看看get(key)做了什么

  public V get(Object key) {    if (key == null)      return getForNullKey();    int hash = hash(key.hashCode());    for (Entry<K,V> e = table[indexFor(hash, table.length)];       e != null;       e = e.next) {      Object k;      if (e.hash == hash && ((k = e.key) == key || key.equals(k)))        return e.value;    }    return null;  }

这些动作似乎是跟put(key，value)相识，通过hash算法获取key的hash码，再通过indexFor定位出该key存在于table的哪一个下表，获取该下标然后对下标中的链表进行遍历比对，如果有符合就直接返回该key的value值。keySet()这里还涉及另一个问题，上面说了HashMap是跟set没有任何亲属关系，但map也一样实现了keySet接口，下面谱析一下keySet在hashMap中是如何实现的，这里给出部分代码，请结合源码查看

public K next() {      return nextEntry().getKey();    }  final Entry<K,V> nextEntry() {      if (modCount != expectedModCount)        throw new ConcurrentModificationException();      Entry<K,V> e = next;      if (e == null)        throw new NoSuchElementException();      if ((next = e.next) == null) {        Entry[] t = table;        while (index < t.length && (next = t[index++]) == null)          ;      }    current = e;      return e;    }

代码很简单，就是对每个格子里面的链表进行遍历，也正是这个原因，当我们依次将key值put进hashMap中，但在使用map.entrySet().iterator()进行遍历时候却不是put时候的顺序。扩容if (size++ >= threshold)    

void resize(int newCapacity) {    Entry[] oldTable = table;    int oldCapacity = oldTable.length;    if (oldCapacity == MAXIMUM_CAPACITY) {      threshold = Integer.MAX_VALUE;      return;    }    Entry[] newTable = new Entry[newCapacity];    transfer(newTable);    table = newTable;    threshold = (int)(newCapacity * loadFactor);  }  void transfer(Entry[] newTable) {    Entry[] src = table;    int newCapacity = newTable.length;    for (int j = 0; j < src.length; j++) {      Entry<K,V> e = src[j];      if (e != null) {        src[j] = null;        do {          Entry<K,V> next = e.next;          int i = indexFor(e.hash, newCapacity);          e.next = newTable[i];          newTable[i] = e;          e = next;        } while (e != null);      }    }  }

transfer方法实际上是将所有的元素重新进行一些hash，这是因为容量变化了，每个元素相对应的hash值也会不一样。使用HashMap1.不要再高并发中使用HashMap，HashMap是线程不安全，如果被多个线程共享之后，将可能发生不可预知的问题。当然啦，HashMap的函数还有很多，不过都是基于table的链表进行操作，当然也就是hash算法，Map & hashMap在平时我们的应用非常多，最重要的是我们要对每句代码中每块数据结构变化心中有数。

 

海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理：https://www.xlkjsw.com

原标题：Java温故而知新（1）

关键词：JAVA