赞
踩
HashMap<String , Double> map = new HashMap<String , Double>(); map.put("语文" , 80.0); map.put("数学" , 89.0); map.put("英语" , 78.2);
public V put(K key, V value) { // 如果key 为null,调用putForNullKey 方法进行处理 if (key == null) return putForNullKey(value); // 根据key 的keyCode 计算Hash 值 int hash = hash(key.hashCode()); // 搜索指定hash 值在对应table 中的索引 int i = indexFor(hash, table.length); // 如果i 索引处的Entry 不为null,通过循环不断遍历e 元素的下一个元素 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 找到指定key 与需要放入的key 相等(hash 值相同通过equals 比较放回true) if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 如果i 索引处的Entry 为null,表明此处还没有Entry modCount++; // 将key、value 添加到i 索引处 addEntry(hash, key, value, i); return null; }
static int hash(int h) { h ^= (h $amp;>amp;>amp;$gt; 20) ^ (h $amp;>amp;>amp;$gt; 12); return h ^ (h $amp;>amp;>amp;$gt; 7) ^ (h $amp;>amp;>amp;$gt; 4); }
static int indexFor(int h, int length) { return h & (length-1); }
void addEntry(int hash, K key, V value, int bucketIndex) { // 获取指定bucketIndex 索引处的Entry Entry<K,V> e = table[bucketIndex]; // ① //将新创建的Entry 放入bucketIndex 索引处,并让新的Entry 指向原来的Entry table[bucketIndex] = new Entry<K,V>(hash, key, value, e); // 如果Map 中的key-value 对的数量超过了极限 if (size++ >= threshold) // 把table 对象的长度扩充到2 倍。 resize(2 * table.length); // ② }
// 以指定初始化容量、负载因子创建HashMap public HashMap(int initialCapacity, float loadFactor) { // 初始容量不能为负数 if (initialCapacity < 0) throw new IllegalArgumentException( "Illegal initial capacity: " + initialCapacity); // 如果初始容量大于最大容量,让出示容量 if (initialCapacity >MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY; // 负载因子必须大于0 的数值 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException(loadFactor); // 计算出大于initialCapacity 的最小的2 的n 次方值。 int capacity = 1; while (capacity < initialCapacity) capacity $amp;<amp;$lt;= 1;="" this.loadfactor="loadFactor;" 设置容量极限等于容量*="" 负载因子="" threshold="(int)(capacity" *="" loadfactor);="" 初始化table="" 数组="" table="new" entry[capacity];="" ①="" init();="" }<="" p="" style="margin: 0px; padding: 0px; list-style: none;">
上面代码中粗体字代码包含了一个简洁的代码实现:找出大于initialCapacity 的、最小的
2 的n 次方值,并将其作为HashMap 的实际容量(由capacity 变量保存)。例如给定
initialCapacity 为10,那么该HashMap 的实际容量就是16。
initialCapacity 与HashTable 的容量创建HashMap 时指定的initialCapacity 并不等于HashMap 的实际容量,通常来说,HashMap 的实际容量总比initialCapacity 大一些,除非我们指定的initialCapacity 参数值恰好是2 的n 次方。当然,掌握了HashMap 容量分配的知识之后,应该在创建HashMap 时将initialCapacity 参数值指定为2 的n 次方,这样可以减少系统的计算开销。
程序①号代码处可以看到:table 的实质就是一个数组,一个长度为capacity 的数组。
对于HashMap 及其子类而言,它们采用Hash 算法来决定集合中元素的存储位置。当系统开始初始化HashMap 时,系统会创建一个长度为capacity 的Entry 数组,这个数组里可以存储元素的位置被称为“桶(bucket)”,每个bucket 都有其指定索引,系统可以根据其索引快速访问该bucket 里存储的元素。
无论何时,HashMap 的每个“桶”只存储一个元素(也就是一个Entry),由于Entry 对象可以包含一个引用变量(就是Entry 构造器的的最后一个参数)用于指向下一个Entry,因此可能出现的情况是:HashMap 的bucket 中只有一个Entry,但这个Entry 指向另一个Entry ——这就形成了一个Entry 链。HashMap 的读取实现.
当HashMap 的每个bucket 里存储的Entry 只是单个Entry ——也就是没有通过指针产生Entry 链时,此时的HashMap 具有最好的性能:当程序通过key 取出对应value时,系统只要先计算出该key 的hashCode() 返回值,在根据该hashCode 返回值找出该key 在table 数组中的索引,然后取出该索引处的Entry,最后返回该key 对应的value 即可。看HashMap 类的get(K key) 方法代码:
public V get(Object key) { // 如果key 是null,调用getForNullKey 取出对应的value if (key == null) return getForNullKey(); // 根据该key 的hashCode 值计算它的hash 码 int hash = hash(key.hashCode()); // 直接取出table 数组中指定索引处的值, for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; // 搜索该Entry 链的下一个Entry e = e.next) // ① { Object k; // 如果该Entry 的key 与被搜索key 相同 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { // 使用HashMap 的key 保存HashSet 中所有元素 private transient HashMap<E,Object> map; // 定义一个虚拟的Object 对象作为HashMap 的value private static final Object PRESENT = new Object(); ... // 初始化HashSet,底层会初始化一个HashMap public HashSet() { map = new HashMap<E,Object>(); } // 以指定的initialCapacity、loadFactor 创建HashSet // 其实就是以相应的参数创建HashMap public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<E,Object>(initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap<E,Object>(initialCapacity); } HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<E,Object>(initialCapacity , loadFactor); } // 调用map 的keySet 来返回所有的key public Iterator<E> iterator() { return map.keySet().iterator(); } // 调用HashMap 的size() 方法返回Entry 的数量,就得到该Set 里元素的个数 public int size() { return map.size(); } // 调用HashMap 的isEmpty() 判断该HashSet 是否为空, // 当HashMap 为空时,对应的HashSet 也为空 public boolean isEmpty() { return map.isEmpty(); } // 调用HashMap 的containsKey 判断是否包含指定key //HashSet 的所有元素就是通过HashMap 的key 来保存的 public boolean contains(Object o) { return map.containsKey(o); } // 将指定元素放入HashSet 中,也就是将该元素作为key 放入HashMap public boolean add(E e) { return map.put(e, PRESENT) == null; } // 调用HashMap 的remove 方法删除指定Entry,也就删除了HashSet 中对应的元素 public boolean remove(Object o) { return map.remove(o)==PRESENT; } // 调用Map 的clear 方法清空所有Entry,也就清空了HashSet 中所有元素 public void clear() { map.clear(); } ... }
class Name { private String first; private String last; public Name(String first, String last) { this.first = first; this.last = last; } public boolean equals(Object o) { if (this == o) { return true; } if (o.getClass() == Name.class) { Name n = (Name)o; return n.first.equals(first) && n.last.equals(last); } return false; } } public class HashSetTest { public static void main(String[] args) { Set<Name> s = new HashSet<Name>(); s.add(new Name("abc", "123")); System.out.println(s.contains(new Name("abc", "123"))); } }
class Name { private String first; private String last; public Name(String first, String last) { this.first = first; this.last = last; } // 根据first 判断两个Name 是否相等 public boolean equals(Object o) { if (this == o) { return true; } if (o.getClass() == Name.class) { Name n = (Name)o; return n.first.equals(first); } return false; } // 根据first 计算Name 对象的hashCode() 返回值 public int hashCode() { return first.hashCode(); } public String toString() { return "Name[first=" + first + ", last=" + last + "]"; } } public class HashSetTest2 { public static void main(String[] args) { HashSet<Name> set = new HashSet<Name>(); set.add(new Name("abc" , "123")); set.add(new Name("abc" , "456")); System.out.println(set); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。