什么是手机网站,广西建设厅招投标中心网站,找人搭建网站多少钱,北京seo薪资java.util包中的集合类包含 Java 中某些最常用的类。最常用的集合类是 List 和 Map。List 的具体实现包括 ArrayList 和 Vector#xff0c;它们是可变大小的列表#xff0c;比较适合构建、存储和操作任何类型对象元素列表。List 适用于按数值索引访问元素的情形。 Map 则提供… java.util包中的集合类包含 Java 中某些最常用的类。最常用的集合类是 List 和 Map。List 的具体实现包括 ArrayList 和 Vector它们是可变大小的列表比较适合构建、存储和操作任何类型对象元素列表。List 适用于按数值索引访问元素的情形。 Map 则提供了一个更通用的元素存储方法。Map 集合类用于存储元素对称作“键”和“值”其中每个键映射到一个值。从概念上而言您可以将 List 看作是具有数值键的 Map。而实际上除了 List 和 Map 都在定义 java.util 中外两者并没有直接的联系。 Map接口的实现类有很多其中HashMap就是比较重要的一个实现本文就以HashMap为主重点介绍。 HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作并允许使用 null 值和 null 键。除了非同步和允许使用 null 之外HashMap 类与 Hashtable 大致相同。此类不保证映射的顺序特别是它不保证该顺序恒久不变。 HashMap结合了ArrayList与LinkedList两个实现的优点虽然HashMap并不会向List的两种实现那样在某项操作上性能较高但是在基本操作get 和 put上具有稳定的性能。 首先从成员变量开始一点点的来了解HashMap和上述几个概念。 1.HashMap的成员变量 Java代码 /** * 初始默认容量必须为2的幂次方 */ static final int DEFAULT_INITIAL_CAPACITY 16; /** * 最大容量,如果被指定为一个更高的值必须为2的幂次方并且小于1073741824.(130) */ static final int MAXIMUM_CAPACITY 1 30; /** * 默认负载因子/负载系数 */ static final float DEFAULT_LOAD_FACTOR 0.75f; /** * 内部实现表, 必要时调整大小其长度亦为2的幂次方 */ transient Entry[] table; /** * map中添加的元素个数 */ transient int size; /** * 扩容临界值当size达到此值时进行扩容 (容量乘以负载因子). */ int threshold; /** * 内部实现表的负载因子 */ final float loadFactor; /** * 操作数可以理解为map实例被操作的次数包括添加删除等等 */ transient volatile int modCount; HashMap其内部实现是一个Entry数组table而Entry就是保存相应键值的实体。table数组默认大小为16我们也可以在初始化时指定更大的值但指定值必须为2的幂次方。 通过对ArrayList的学习了解到ArrayList其内部实现也是数组当被添加的元素超出数组的容纳极限时ArrayList会对内部数组进行一次“扩容”从而可以添加新的元素。 在HashMap中也有类似的概念HashMap并不会像ArrayList一样直到数组都满了的情况下才去“扩容”而是根据负载因子load factor来进行判断。 举例来说HashMap实例中table数组的默认大小为16负载因子为0.75当添加元素个数大于等于1216*0.75时就会进行扩容。 所以说容量和负载因子直接影响着table数组是否扩容什么时机扩容进而影响这HashMap实例的性能。 当我们在初始化时可以指定HashMap实例的容量大小当指定大小不为2的幂次方时如下 Java代码 Map mapnew HashMap(131); 请问初始化完成HashMap内table的长度是多少 答案为256 其实只要打开HashMap的构造函数源代码就明白为什么了以下为源代码 Java代码 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(); } 关键在于这两行 Java代码 while (capacity initialCapacity) capacity 1; 如果initialCapacity指定大小大于capacity原或初始化大小时就会不断循环进行位移赋值计算相当于capacitycapacity *2.直至capacity 大于或等于我们指定的大小。如果指定的大小正好为2的N次幂时两个值便会相等进而终止计算如果指定大小不符合条件时capacity 就会是刚好大于指定大小的那个2的N次幂的数。 所以在上面我们指定大小为131大于131并且为2的的N次幂的数就为256所以此时就会按256来初始化table. 2.Entry 元素 与LinkedList类似HashMap也是采用Entry内部类来存储实际元素信息以下是Entry的源代码省略部分代码 Java代码 static class EntryK, V implements Map.EntryK, V { final K key; V value; EntryK, V next; final int hash; } Entry中包括4个成员变量其中key为键value为值next指向下一个节点元素hash为hash值。Entry通过next属性可以寻找到下一个节点的元素进而通过遍历就可以找到相应key下存储的信息。 3.HashMap设置元素 Map通过put方法来在Map实例中关联指定值与指定键。如果该实例已经包含了一个该键的映射关系则旧值被替换。 示例如下 Java代码 Map map new HashMap(); map.put(user1, 小明); map.put(user2, 小强); map.put(user3, 小红); System.out.println(user1: map.get(user1)); System.out.println(user2: map.get(user2)); System.out.println(user3: map.get(user3)); map.put(user2, 小龙); System.out.println(user1: map.get(user1)); //打印结果 user1:小明 user2:小强 user3:小红 user1:小明 首先创建了一个HashMap的实例map此时map实例中的table数组会默认初始化创建一个长度为DEFAULT_INITIAL_CAPACITY16的空数组。 然后调用put方法将一对键、值key,value保存。当已存在Map实例中已存在指定key的映射时会将新指定的value覆盖原value。 与LIst的相关实现add方法一样HashMap的put方法是设置元素的入口在put的过程中会进行一系列的判断与操作所以只有将put方法理解透彻后HashMap的内部结构与机制才会更加清晰。 HashMap进行put操作时按以下步骤执行 1判断key是否为空如果为空则调用设置null的专有方法。 2计算key的hash值。 3通过hash与table数组的长度计算出该元素所要放置的数组下标。 4遍历该下标下的Entry元素链如果找到与指定key相同的Entry则直接替换该Entry的value值并返回。 5如果未找到则添加一个新元素至该下标下的元素链前端。 以下是一张官网上对于put操作流程的描述图片可以作为参考 以下是put方法的源代码其中我已经加入了相关描述便于大家理解 Java代码 /** * 设置指定值 */ public V put(K key, V value) { //1.首先判断key是否为null if (key null) //如果为null则调用putForNullKey方法 return putForNullKey(value); //2.计算key的hash值 int hash hash(key.hashCode()); //3.根据计算后的hash值与table数组长度计算该key应放置到table数组的那个下标位置 int i indexFor(hash, table.length); //4.遍历该下标下的所有Entry如果key已存在则覆盖该key所在Entry的value值 for (EntryK, 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; //5.如果该key不存在则新添加Entry元素至数组指定位置并且该Entry作为此下标元素链的头部 addEntry(hash, key, value, i); return null; } 4.HashMap内部结构 通过对put方法的流程分析我们基本已经了解HashMap其内部实现的机制与原理那么来总结一下HashMap初始化及添加元素的过程以默认值为例 (1) 初始化HashMap实例初始化其内部数组table Java代码 this.loadFactor DEFAULT_LOAD_FACTOR;//0.75f threshold (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);//16*0.7512 table new Entry[DEFAULT_INITIAL_CAPACITY];//16 此时table被初始化创建长度为16。 (2) 当第一次put元素时此时HashMap实例中并没有添加任何元素所以put方法会直接调用addEntry方法 Java代码 EntryK,V e table[bucketIndex]; table[bucketIndex] new EntryK,V(hash, key, value, e); 首先会先获取该下标bucketIndex下原Entry信息因为table并未设置任何值所以此时e为null。 然后创建一个新的Entry实例其next属性指向e并将此实例赋值给table[bucketIndex]。 (3) 当更新HashMap实例中已有key的value内容时 Java代码 for (EntryK,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; } } 如果HashMap实例中已经put了该key则只需遍历找到该节点Entry更新其value并返回所以更新已有key的操作不会调用addEntry方法。 (4) 此时HashMap实例的内部结构如下图所示 HashMap采用此种存储元素的方式是结合了ArrayList与LinkedList两者的优点虽然单纯某项操作的性能上并不比二者之一高但这种方式的好处就是存储与获取性能平稳并不会出现剧烈波动的情况。 5.HashMap获取元素 既然已经了解了HashMap的内部结构已经设置元素时的相关操作步骤那么获取元素其实也就比较容易理解了首先根据指定的key去计算数组下标然后遍历该下标下的Entry链最后返回。 以下是get方法的源代码与put方法的基本流程大致相同 Java代码 /** * 返回指定key的value */ public V get(Object key) { // 1.判断可以是否为null if (key null) return getForNullKey(); // 2.计算key的hash值 int hash hash(key.hashCode()); // 3.遍历table指定下标下的Entry链 for (EntryK, V e table[indexFor(hash, table.length)]; e ! null; e e.next) { Object k; // 4.如果找到则返回该Entry的value if (e.hash hash ((k e.key) key || key.equals(k))) return e.value; } // 5.未找到则返回null return null; } 6.HashMap移除元素 HashMap实现了Map接口的remove方法所以可以通过remove方法移除已经添加的元素 Java代码 Map map new HashMap(); map.put(user1, 小明); map.put(user2, 小强); map.put(user3, 小红); map.remove(user2); System.out.println(user1: map.get(user1)); System.out.println(user2: map.get(user2)); System.out.println(user3: map.get(user3)); //打印结果 user1:小明 user2:null user3:小红 当主动调用remove方法时会根据指定的key删除该节点元素。 以下是remove方法的源代码 Java代码 /** * 删除指定key下内容 */ public V remove(Object key) { EntryK, V e removeEntryForKey(key); return (e null ? null : e.value); } /** * 根据指定key删除元素 */ final EntryK, V removeEntryForKey(Object key) { int hash (key null) ? 0 : hash(key.hashCode()); int i indexFor(hash, table.length); EntryK, V prev table[i]; EntryK, V e prev; while (e ! null) { EntryK, V next e.next; Object k; if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) { modCount; size--; if (prev e) table[i] next; else prev.next next; e.recordRemoval(this); return e; } prev e; e next; } return e; } remove方法调用了另一个方法removeEntryForKeyremoveEntryForKey方法会循环遍历指定下标下所有Entry节点元素如果该key存在则修改该节点前一个节点的next指向从而达到把该Entry节点移除Entry链的目的。 注意HashMap的remove操作一样不会引起“减容”操作这样就不会影响性能。 7.HashMap的遍历 通常情况下Map的使用者清楚该Map实例中有那些key通过get(key)方法就可以直接将所有元素取出但某些情况下这种做法产生的代码将是一次性代码无法共用。 HashMap的遍历通常采用以下几种方式 1通过entrySet()方法可以获取HashMap实例所有Entry的Set返回所以通过entrySet方法返回并迭代可以获取所有Entry元素 Java代码 Map map new HashMap(); map.put(user1, 小明); map.put(user2, 小强); map.put(user3, 小红); Iterator iter map.entrySet().iterator(); while (iter.hasNext()) { Map.Entry entry (Map.Entry) iter.next(); Object key entry.getKey(); Object value entry.getValue(); System.out.println(key: key ;value: value); // 然后移除元素 if (key.toString().equals(user1)) { iter.remove(); } else if (key.toString().equals(user2)) { entry.setValue(小海); } } System.out.println(map.get(user1)); System.out.println(map.get(user2)); System.out.println(map.get(user3)); // 打印结果 key:user2;value:小强 key:user1;value:小明 key:user3;value:小红 null 小海 小红 此种方式操作简单代码量少效率较高且可以直接操作元素是常用的手段之一。 2Map还提供了keySet方法用于返回所有key的Set形式然后迭代此Set再通过get方法就可以获取相应元素的value Java代码 Map map new HashMap(); map.put(user1, 小明); map.put(user2, 小强); map.put(user3, 小红); Iterator iter map.keySet().iterator(); while (iter.hasNext()) { Object key iter.next(); Object value map.get(key); System.out.println(key: key ;value: value); // 然后移除元素 if (key.toString().equals(user1)) { iter.remove(); } } System.out.println(map.get(user1)); System.out.println(map.get(user2)); System.out.println(map.get(user3)); // 打印结果 key:user2;value:小强 key:user1;value:小明 key:user3;value:小红 null 小强 小红 此种方式先需要将所有key遍历后返回再通过get方法来获取元素如果单纯需要操作Map实例中的个别节点元素时效率尚可如果需要大规模获取和修改时效率不如第一种。所以两种方式选择那种需要视情况而言并没有绝对。 3通过values方法直接返回所有value Java代码 Map map new HashMap(); map.put(user1, 小明); map.put(user2, 小强); map.put(user3, 小红); //转换成数组 String[] names (String[]) map.values().toArray(new String[map.size()]); for (String name : names){ System.out.println(name); } //采用迭代 Collection nameArray map.values(); Iterator iter nameArray.iterator(); while (iter.hasNext()) { String nameiter.next().toString(); System.out.println(name); } // 打印结果 小强 小明 小红 此种方式简单明了适用于直接获取所有value的情况可以直接迭代或者转换成数组当直接显示value的情况下比较适用。 HashMap的基本结构及内部实现原理至此已经比较清晰下一篇着重来了解下HashMap其内部几种算法的原理及相关性能。 http://286.iteye.com/blog/2187873
