1. 使用shuffle打乱列表
在网站上我们经常看到关键字云和标签云等，用于表明这个关键字或标签经常被查阅。我
使用swap实现：
public static void main(String[] arg) {
int tagCloudNum = 10;
List<String> tagfClouds = new ArrayList<>(tagCloudNum);
Random rand = new Random();
for(int i=0;i<tagCloudNum;i++){
int randomPosition = rand.nextInt(tagCloudNum);
Collections.swap(tagfClouds,i,randomPosition);
}
}
最优的使用shuffle实现：
public static void main(String[] arg) {
int tagCloudNum = 10;
List<String> tagfClouds = new ArrayList<>(tagCloudNum);
//打乱顺序
Collections.shuffle(tagfClouds);
}
2. 减少HashMap中元素的数量
在系统开发中我们经常会使用HashMap作为数据集容器,或者是用缓冲池来处理,一般很稳定,但偶尔也会出现内存溢出的问题(OutOfMemory错误),而且这经常是与HashMap有关的.而且这经常是与HashMap有关的.比如我们使用缓冲池操作数据时,大批量的增删改产操作就可能会让内存溢出,下面建立一段模拟程序,重现该问题,看代码:
import java.util.HashMap;
import java.util.Map;
public class Client {
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
final Runtime rt = Runtime.getRuntime();
// JVM终止前记录内存信息
rt.addShutdownHook(new Thread() {
@Override
public void run() {
StringBuffer sb = new StringBuffer();
long heapMaxSize = rt.maxMemory() >> 20;
sb.append("最大可用内存：" + heapMaxSize + "M\n");
long total = rt.totalMemory() >> 20;
sb.append("对内存大小：" + total + "M\n");
long free = rt.freeMemory() >> 20;
sb.append("空闲内存：" + free + "M");
System.out.println(sb);
}
});
// 放入40万键值对
for (int i = 0; i < 40*10000; i++) {
map.put("key" + i, "vlaue" + i);
}
}
}
运行结果如下：
Exception in thread "main" 最大可用内存：63M
对内存大小：63M
空闲内存：7M
java.lang.OutOfMemoryError: Java heap space
at java.util.HashMap.resize(Unknown Source)
at java.util.HashMap.addEntry(Unknown Source)
at java.util.HashMap.put(Unknown Source)
at cn.summerchill.test.Client.main(Client.java:26)
内存溢出了....可能认为在运行时增加"-Xmx"参数设置内存大小就可以了,这确实可以,不过浮于表面,没有真正的从溢出的最根本原因上来解决问题.难道的是String字符串太多了?字符串对象对象加起来撑死最多10MB,而且这里还空闲了7MB内存,不应该报内存溢出？
或者是put方法有缺陷,产生了内存泄漏?不可能...这里还有7MB的内存可用,应该要用尽了才会出现内存泄漏啊
用ArrayList做一个对比,把相同数据插入到ArrayList中看看会怎么样,看代码:
import java.util.ArrayList;
import java.util.List;
public class Client {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
final Runtime rt = Runtime.getRuntime();
// JVM终止前记录内存信息
rt.addShutdownHook(new Thread() {
@Override
public void run() {
StringBuffer sb = new StringBuffer();
long heapMaxSize = rt.maxMemory() >> 20;
sb.append("最大可用内存：" + heapMaxSize + "M\n");
long total = rt.totalMemory() >> 20;
sb.append("对内存大小：" + total + "M\n");
long free = rt.freeMemory() >> 20;
sb.append("空闲内存：" + free + "M");
System.out.println(sb);
}
});
// 放入40万同样字符串
for (int i = 0; i < 400000; i++) {
list.add("key" + i);
list.add("vlaue" + i);
}
}
}
运行输出:
最大可用内存：63M
对内存大小：63M
空闲内存：11M
ArrayList运行很正常,没有出现内存溢出的情况,两个容器,容纳的元素相同,数量相同,ArrayList没有溢出,但HashMap却溢出了,很明显,这与HashMap内部的处理机制有很大的关系.
HashMap在底层也是以数组方式保存元素的,其中每一个键值对就是一个元素 ,也就是说HashMap把键值对封装成了一个Entry对象,然后再把Entry放到了数组中,我们简单看一下Entry类:java.util.HashMap.Entry<K, V>
static class Entry<K,V> implements Map.Entry<K,V> {
//键
final K key;
//值
V value;
//相同哈希码的下一个元素
Entry<K,V> next;
final int hash;
//key,value的getter和setter方法,以及重写的equals,hashCode,toString方法
}
HashMap底层的数组变量名叫table,它是Entry类型的数组,保存的是一个个的键值对(在我们的例子中Entry是由两个String类型组成的).对我们的例子来说,HashMap比ArrayList多了一次封装,把String类型的键值对转换成Entry对象后再放入数组,这就多了40万个对象,这应该是问题产生的一个原因.
我们知道HashMap的长度也是可以动态增加的,它的扩容机制与ArrayList稍有不同,其代码如下:
if (size++ >= threshold)
resize(2 * table.length);
在插入键值对时,会做长度校验,如果大于或等于阀值(threshold变量),则数组长度增大一倍,不过,默认的阀值是多大呢?默认是当前长度与加载因子的乘积.
threshold = (int) (newCapacity * loadFactory);
默认的加载因子(loadFactor变量)是0.75,也就是说只要HashMap的size大于数组长度的0.75倍时,就开始扩容,经过计算得知(怎么计算,查找2的N次方大于40万的最小值即为数组的最大长度,再乘以0.75就是最后一次扩容点,计算的结果是19),
在Map的size为393216时,符合了扩容条件,于是393216个元素准备开始大搬家,那就要首先申请一个长度为1048576(当前长度的两倍,2的19次方再乘以2,即2的20次方)的数组,但问题是此时剩余的内存只有7Mb了.不足以支撑此时的运算.于是就报内存溢出了.这是第二个原因,也是最根本的原因.
这就解释了为什么还剩余7MB的时候就报内存溢出了.
再考虑下ArrayList的扩容策略,它是在小于数组长度的时候才会扩容1.5倍,经过计算得知,ArrayList的size在超过80万后(一次加两个元素,40万的两倍),最近的一次扩容会在size为1005308时,也就是说,如果程序设置了增加元素的上限为502655,同样会报内存溢出,因为他也要申请一个1507963长度的数组.如果没有这么大的地方,就报错了.
综合来说,HashMap比ArrayList多了一个层Entry的底层对象封装,多占用了内存,并且它的扩容策略是2倍长度的递增,同时还会依据阀值判断规则进行判断,因此相对于ArrayList来说,它就会先出现内存溢出.
3. 从源码分析HashSet / HashMap是如何保证不重复的
HashSet.add()调用的是HashMap.put()。HashMap判断依据是key值。映射到一个hash桶，当key值相等时，替换掉旧值，不相等就追加节点。这样保证了一个HashMap里key值是唯一的。从而相同key值的元素只有一份，保证其唯一
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;
......
public boolean add(E e) {
//用了HashMap的put
return map.put(e, PRESENT)==null;
}
}
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
......
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/* n是表的大小，是2的整次幂，初始大小是16.
* (n - 1) & hash相当于对表大小取余，即i是下标
* tab[i]=null即这个桶是空的，直接newNode即可
* p如果不空则赋值为链表头，第一个节点
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//桶不空即链表至少有一个节点
else {
Node<K,V> e; K k;
//如果key相同则赋给e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果桶里不是链表而是红黑树，那根据hash值放入红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//它是链表并且需要寻找下一个节点进行比较
else {
for (int binCount = 0; ; ++binCount) {
//链表到头没找着key相同的，要新增
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//链表的节点总数 >= 8变成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//找到相等的，不必再往下，跳出for循环
//如果不跳出，e最后一定等于null
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//和前面if里的e=p.next配合，往前一个
p = e;
}
}
//e是找到的那个链表里的旧的
if (e != null) {
V oldValue = e.value;
//onlyIfAbsent不可更新开关，put默认false
//可更新 或 原值为空，则替换为新值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}//end else桶空情况
//全局修改次数+1
++modCount;
//size+1 > 阈值（capacity * load factor）
if (++size > threshold)
resize();
//对HashMap来说是空方法，是LinkedHashMap用的
afterNodeInsertion(evict);
return null;
}
}
4. 非稳定排序推荐使用List
我们知道Set与List的区别就是Set中元素不可以重复（这个重复是指equals方法的返回值相等），其它方面没有太大的区别。在Set的实现类里有一个TreeSet，该类实现了类默认排序为升序的Set集合，如果插入一个元素，默认会按升序排列（当然是根据Comparable接口的compareTo的返回值确定排序位置）
import java.util.SortedSet;
import java.util.TreeSet;
public class Client {
public static void main(String[] args) {
SortedSet<Person> set = new TreeSet<Person>();
//身高180CM
set.add(new Person(180));
//身高175CM
set.add(new Person(175));
for(Person p:set){
System.out.println("身高:"+p.getHeight());
}
}
static class Person implements Comparable<Person>{
//身高
private int height;
public Person(int _age){
height = _age;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
//按照身高排序
public int compareTo(Person o) {
return height - o.height;
}
}
}
结果：
身高:175
身高:180
但是如果在插入元素后再修改某个元素的值，那么Set不会重新排序。
public static void main(String[] args) {
SortedSet<Person> set = new TreeSet<Person>();
// 身高180CM
set.add(new Person(180));
// 身高175CM
set.add(new Person(175));
// 身高最矮的人大变身
set.first().setHeight(185);
for (Person p : set) {
System.out.println("身高:" + p.getHeight());
}
}
结果：
身高:185
身高:180
解决方法如下：
- Set集合重排序，重新生成一个Set对象，也就是对原有Set对象重新排序，
set = new TreeSet<Person>(new ArrayList<Person>(set))。为什么不使用TreeSet<SortedSet<E> s>这个构造函数？不行，该构造函数只是原Set的浅拷贝，如果里面有相同的元素则不进行排序
import java.util.ArrayList;
import java.util.SortedSet;
import java.util.TreeSet;
public class Client {
public static void main(String[] args) {
SortedSet<Person> set = new TreeSet<Person>();
// 身高180CM
set.add(new Person(180));
// 身高175CM
set.add(new Person(175));
// 身高最矮的人大变身
set.first().setHeight(185);
//set重排序
set = new TreeSet<Person>(new ArrayList<Person>(set));
//set = new TreeSet(set);该构造函数只是原Set的浅拷贝，如果里面有相同的元素，是不会重新排序的
for (Person p : set) {
System.out.println("身高:" + p.getHeight());
}
}
static class Person implements Comparable<Person> {
// 身高
private int height;
public Person(int _age) {
height = _age;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
// 按照身高排序
public int compareTo(Person o) {
return height - o.height;
}
}
}
- 如果不考虑重复，可以使用List实现，用Collections.sort()进行排序
