static class Entry<K,V> implements Map.Entry<K,V> { final K key; //键 V value; //值 Entry<K,V> next;//链表下一个 int hash; //hash值 Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }
public final K getKey() { return key; }
public final V getValue() { return value; }
public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; }
public V put(K key, V value) { //如果table是空的，初始化一下数组 if (table == EMPTY_TABLE) { inflateTable(threshold); } //如果key 为空，放空值 if (key == null) return putForNullKey(value); int hash = hash(key);//计算hash值 int i = indexFor(hash, table.length);//计算下标
//这个for循环很重要，目的是找到hash值相同且key相同的entry，然后覆盖 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; } } //如果不覆盖，则增加一个新的entry modCount++; addEntry(hash, key, value, i); return null; }
//增加一个entry（），hash值，key值，value，当前的下标 void addEntry(int hash, K key, V value, int bucketIndex) { //当到达了threshold值，切当前这个table[bucketIndex]值不为空，触发增长 if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length);//扩容，已2倍数组长度增长 hash = (null != key) ? hash(key) : 0; //因为数组增长了，重新计算hash值 bucketIndex = indexFor(hash, table.length); //在新数组里边的bucketIndex }
public class Hash{ @Test public void testHash() throws NoSuchFieldException, IllegalAccessException, ClassNotFoundException { //创建一个数据,用户存放key String[] strings = new String[52]; for (int i = 0; i < strings.length; i++) { char c = (char) (i + 65); strings[i] = String.valueOf(c + "asdke"); } HashMap<String, String> stringStringHashMap = new HashMap<>();
// Field loadFactor = stringStringHashMap.getClass().getDeclaredField("loadFactor"); // loadFactor.setAccessible(true); // loadFactor.set(stringStringHashMap, Float.valueOf(0.5F));
Field table = stringStringHashMap.getClass().getDeclaredField("table"); table.setAccessible(true); System.out.println("index"+" "+"key" + " " + "length" + " " + "bucketIndex"); for (int i = 0; i < strings.length; i++) { String string = strings[i]; stringStringHashMap.put(string, "aa"); //获取table值 Object[] o = (Object[]) table.get(stringStringHashMap); //对应table长度 System.out.println(i+" -- "+string + " -- " + o.length + " -- " + (hash(string) & (o.length - 1))); } //获取table值 Object[] o = (Object[]) table.get(stringStringHashMap); for (int i = 0; i < o.length; i++) { Object o1 = o[i]; if (o1 == null) { continue; } List<Object> list = new ArrayList<>(); //遍历entry链表，放入list中 next(o1, list); //打印链表 System.out.println("entry " + o1 + " next " + list.toString()); } System.out.println(stringStringHashMap.toString()); }
/** * 遍历entry * @param target * @param list * @throws ClassNotFoundException * @throws NoSuchFieldException * @throws IllegalAccessException */ private void next(Object target, List<Object> list) throws ClassNotFoundException, NoSuchFieldException, IllegalAccessException { Class c = Class.forName("java.util.HashMap$Entry"); Field next = c.getDeclaredField("next"); next.setAccessible(true); Object o2 = next.get(target); if (o2 == null) { return; } list.add(o2); next(o2, list); }
