HashMap 是一种十分常用的数据结构对象,可以保存键值对。它在项目中用的比较多,今天我们就来学习一下关于它的知识。
- Map map = new HashMap < >();
- map.put("username", "huhx");
- map.put("password", "1234");
- map.put(null, null);
- System.out.println(map.put("username", "linux")); // huhx,这里会返回
- System.out.println(map.get("username")); // linux
- System.out.println(map.get(null) + " size: " + map.size()); // null size: 3
put(key, value) 方法如果 map 中存在根据 hash 计算 key 的值。那么返回的结果是 map 中 oldValue 值。但是 map 里面的 key 对应的值更新成了 value 值。
- public voidputAll(MapextendsK,extendsV> m) {
- ......
- for(Map.EntryextendsK,extendsV> e : m.entrySet())
- put(e.getKey(), e.getValue());
- }
clear() 方法会清空 map 里面所有的数据,map 的大小为 0。
- public void clear() {
- modCount++;
- Arrays.fill(table, null);
- size = 0;
- }
注意以下的两个方法是接着上述的 map 而言的。
- System.out.println(map.remove("username") + ", size: " + map.size()); // linux, size: 2
- System.out.println(map.remove("nokey") + ", size: " + map.size()); // null, size: 2
源码的方法 remove 方法如下:
- public V remove(Object key) {
- Entry e = removeEntryForKey(key);
- return(e ==nullnull : e.value);
- }
检查是否 map 中存在对应的 key。
- public boolean containsKey(Object key) {
- returngetEntry(key) !=null;
- }
Map<String, String> map = new HashMap<>(); 我们 Map 用到了泛型,这里注明一下。
- Iterator> iterator = map.entrySet().iterator();
- while (iterator.hasNext()) {
- Map.Entry entry = iterator.next();
- String key = entry.getKey();
- String value = entry.getValue();
- System.out.println("key=" + key + " value=" + value);
- }
- for(Map.Entry entry : map.entrySet()) {
- String key = entry.getKey();
- String value = entry.getValue();
- System.out.println("key=" + key + " value=" + value);
- }
- for (String key : map.keySet()) {
- System.out.println("key=" + key + " value=" + map.get(key));
- }
对于以上的各种,由于 map 可以存储 key 为 null 的数据。所以在遍历 map 取 key 的时候,如果是 string。最好是 cast 强转,而不是调用 toString() 方法。
一、hashMap 的数据存储在一个 Entry 数组中,new HashMap(); 会设置 hashMap 的初始容量为 16,负载因子为 0.75。
- publicHashMap(intinitialCapacity,float loadFactor) {
- if(initialCapacity < 0)
- throw newIllegalArgumentException("Illegal initial capacity: " + initialCapacity);
- if(initialCapacity > MAXIMUM_CAPACITY)
- initialCapacity = MAXIMUM_CAPACITY;
- if(loadFactor <= 0 || Float.isNaN(loadFactor))
- throw newIllegalArgumentException("Illegal load factor: " + loadFactor);
- this.loadFactor = loadFactor;
- threshold = initialCapacity;
- init();
- }
其中 init() 方法可以供实现 HashMap 的子类重写,当初始化 map 时增加自己的处理逻辑。hashMap 里面的数据都是通过以下的数组完成的,正因为是数组,所以效率比较高。
- transientEntry[] table = (Entry[]) EMPTY_TABLE;
二、hashMap 主要涉及键值对的 put 和 get,这里我们讨论它的 put 方法
- 1 public V put(K key, V value) {
- 2
- if (table == EMPTY_TABLE) {
- 3 inflateTable(threshold); // 如果table数组为空,就初始化为大小为16,负载因子为0.75的数组。
- 4
- }
- 5
- if (key == null) 6
- return putForNullKey(value);
- 7 int hash = hash(key); // 根据key,计算它的hash值
- 8 int i = indexFor(hash, table.length);
- 9
- for (Entry e = table[i]; e != null; e = e.next) {
- 10 Object k;
- 11
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- 12 V oldValue = e.value;
- 13 e.value = value;
- 14 e.recordAccess(this);
- 15
- return oldValue;
- 16
- }
- 17
- }
- 18 19 modCount++; // 记录hashMap改变的次数
- 20 addEntry(hash, key, value, i);
- 21
- return null;
- 22
- }
第 9 行到 15 行,处理的是 put 的 key 已经存在时,处理的逻辑。就是返回 oldValue,更新 key 的新值为 value。这里我们主要看 addEntry 方法。
- voidaddEntry(inthash, K key, V value,int bucketIndex) {
- if((size >= threshold) && (null!= table[bucketIndex])) {
- resize(2 * table.length);
- hash = (null!= key) ? hash(key) : 0;
- bucketIndex = indexFor(hash, table.length);
- }
- createEntry(hash, key, value, bucketIndex);
- }
由于 hashMap 里面维护的数组在创建的时候,大小为 16。当 key 越来越多的时候,明显计算的 bucketIndex(table 数组的下标) 会重复。也就是 bucketIndex 即将要插入的位置已经有了数据。当发生这种情况时,会增加一倍 hashMap 的容量,重新计算 hash 和要插入数组的位置。最后的 createEntry 方法如下,把 key,value 的值存放到 table 数组中。
- voidcreateEntry(inthash, K key, V value,int bucketIndex) {
- Entry e = table[bucketIndex];
- table[bucketIndex] =newEntry<>(hash, key, value, e);
- size++;
- }
以下附上 hashMap 的 get 代码:
- public V get(Object key) {
- if(key ==null)
- return getForNullKey();
- Entry entry = getEntry(key);
- return null== entrynull : entry.getValue();
- }
table 数组的数据类型 Entry 类如下:
Entry
- static classEntry implementsMap.Entry {
- final K key;
- V value;
- Entry next;
- int hash;
- /**
- * Creates new entry.
- */
- Entry(inth, K k, V v, Entry 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 final boolean equals(Object o) {
- if(!(oinstanceof Map.Entry))
- return false;
- Map.Entry e = (Map.Entry)o;
- Object k1 = getKey();
- Object k2 = e.getKey();
- if(k1 == k2 || (k1 !=null&& k1.equals(k2))) {
- Object v1 = getValue();
- Object v2 = e.getValue();
- if(v1 == v2 || (v1 !=null&& v1.equals(v2)))
- return true;
- }
- return false;
- }
- public final int hashCode() {
- returnObjects.hashCode(getKey()) ^ Objects.hashCode(getValue());
- }
- public final String toString() {
- returngetKey() + "=" + getValue();
- }
- /**
- * This method is invoked whenever the value in an entry is
- * overwritten by an invocation of put(k,v) for a key k that's already
- * in the HashMap.
- */
- voidrecordAccess(HashMap m) {
- }
- /**
- * This method is invoked whenever the entry is
- * removed from the table.
- */
- voidrecordRemoval(HashMap m) {
- }
- }
来源: http://www.cnblogs.com/huhx/p/baseusejavahashmap1.html