这段时间在读《java程序性能优化》，看到里面有一些关于Java的一些数据结构相关的内容，主要涉及到String字符串类型和Map、List、Set等常用的数据结构的一些使用小技巧。感觉在平时的开发中还是很实用的，这里做一些延伸总结，记录一下。
Part I.String字符串优化处理
1.1 String的实现介绍
Java中的String对象实现是通过对Char数组的扩展和进一步封装实现的。它主要由三部分组成：Char数组、偏移量和String的长度。看下图源码中String的构造函数可以明了的看出。Char value[]数组就是String的内容，它是String对象所表示的字符串的超集，意味着假如你定义了一个字符串String=”abc”，其实value[]数组其实可能不单单就是一个长度为3的存在a,b,c三个字符的数组，长度可能是4或者其他值，只不过其他位置没存值。String的真实内容还需要用偏移量和长度在这个value[]数组中去定位和截取。这点是平时很容易忽略的，但是知道这点对后面要讲的String的一些字符串处理方法的性能和内存泄漏的理解很有帮助。
String对象有三个基本特点：
■不变性；
■针对常量池的优化；
■类的final定义；
1.不变性是指String对象一旦生成了，就不能在对它进行改变。这个不变性其实和并发模式里面的不变模式异曲同工，有很多共通的地方。即一个对象一旦创建了，就不会再发生改变，并发的不变模式主要用在当一个对象需要被多个线程共享的时候，并且访问很频繁，这个时候不变性可以保证省略同步和锁的情况下仍是线程安全的，从而大幅度提高系统性能
这里既然顺便扩展介绍一下不变模式：不变模式就是依靠对象的不变性，确保在没有同步操作的多线程环境中依然始终保持内部状态一致性和正确性。不变模式的实现很简单，为了确保对象一旦被创建就不会再被改变只要在创建对象时做到下面几点：
①去除setter方法以及所有修改自身属性的方法。
②将所有的属性设置为私有，并用final标记，确保其不可修改性。
③确保没有子类可以重载修改它的方法。
④有一个可创建完成对象的构造函数。
举个栗子吧,实现一个产品对象，有序列号，名称，价格三个属性：
public final class Product{
private final String no;
private final String name;
private final double price;
public Product (String no ,String name, double price){
Super();
this.no =no;
this.name=name;
this.price=price;
}
public String getNo(){
return no;
}
public String getName(){
return name;
}
public double getPrice(){
return price;
}
}
在不变模式中final关键字起到了重要作用，不管是上面这个例子还是String的定义，都用到final关键字。对class的final定义保证了不变类没有子类，确保了它里面的所有getter方法不会被重写。对属性值的fianl定义确保所有的数据只能在对象被构造时赋值一次，之后就不会再发生改变。我们可以看到String类的定义是完全符合以上这些要求的。
2.针对常量池的优化，当两个String对象拥有相同的值得时候，它们只引用常量池中的同一个拷贝。这个在同一个字符串反复出现时，可以大幅度节省内存空间。这里的常量池就是JVM中的常量池那个内存区域，需要注意的是当你使用new String("")方式创建的字符串时，会被存在堆中，因为对象实例都是存放在堆上。
String str1="abc";
String str2="abc";
String str3=new String("abc");
定义这三个变量，str1 == str2返回true，str1 == str3返回false，str1 == str3.intern()返回true。因为str3使用的new方法重新定义的，所以单独在堆上开辟了一块新的存储空间，所以str1和str3是不相等的，但实际上str3指向的实体str1一样，都是存在常量池中的“abc”，所以当str3.intern()返回String对象在常量池中的引用时，值和str1是一样的。
3.类的final定义，用final关键字定义的类不可能有任何子类，从上面介绍不变性时已经讲了，这样可以保证多线程下的安全性。
1.2 String使用需要注意的地方
由于String对象是不可变对象，所以在对字符串进行修改操作时，比如说字符串拼接，替换时，String对象总是会生成新的对象，所以性能较差。针对字符串修改较多的操作，我们应该使用StringBuffer和StringBuilder类。
实际使用中，对String对象的“+”和“+=”操作其实都会在运行时编译成StringBuilder的实现。但是当这种“+”和“+=”的操作出现在循环体中时，如果还是使用String的话，就会针对每次的“+”和“+=”操作都new一个StringBuilder对象，影响系统性能。所以在实际编码中，尽量少用String的“+”和“+=”操作，String的concat()方法效率也要远高于“+”和“+=”运算符，但和StringBuilder类的效率比起来还是要相差很远。
1.3 StingBuilder和StringBuffer的区别
通过查看源码可以发现其实这两个类实现的方法都差不多，只不过StringBuffer对几乎所有的方法都做了同步处理，而StringBuilder并没有做同步处理。因为做方法同步会对性能有一定的影响，所以StringBuilder的效率要优于StringBuffer，但是在多线程系统中，StringBuilder无法保证线程安全。
在初始化StringBuilder和StringBuffer时都可以预先设置一个容量参数，如果可以预先预测到大小时，可以设置一个初始容量。因为扩容函数的策略是将原有的容量翻倍，创建一个新的数组，然后将原有的数组中的内容复制到这个新的数组中去。
Part II.List类型
List有三种最常用也是最重要的实现就是，ArrayList、Vector和LinkedList。以LinkedList的类图为例。这三种List都是来自AbstractList的实现，AbstracList直接实现了List接口，并扩展自AbstractCollection。
需要注意的是，三种List的实现并不完全一样，ArrayList和Vector使用了数组实现，可以理解为这两种List里面的方法其实是封装好的对内部数组的操作。对这两种List的操作等价于对内部数组的操作。而LinkedList则是使用双向循环链表实现的。这两种不同的实现方式决定了他们适用于不一样的工作场景。ArrayList和Vector几乎使用了相同的算法，唯一的区别就是对多线程的支持。ArrayList中没有对方法进行线程同步处理，因此不是线程安全的。Vector中绝大部分方法都是做了线程同步的，是一种线程安全的实现。
所以我们主要是要对比ArrayList和LinkedList的实现区分两者更适用的场景。
操作一：在任意位置做插入操作。
这是ArrayList的实现，可以看出里面需要先确定数组容量是否足够，不够的话涉及到扩容的处理，扩容需要重新创建一个数组并且将整个数组复制过去。在不需要扩容的情况下，对ArrayList的每一次插入操作也会涉及到一个数组复制，只有在插入List的尾端时，这个操作才不消耗资源。而且如果插入的元素位置越靠前，数组的重组开销也越大。试想一下假设数组很大，此时要在List的头部位置插入数值，这种操作是相当耗费资源和时间的。
这是LinkedList的add函数的实现。对于使用双向循环链表实现的LinkedList来说，不管在哪个位置插入都是一样的。因为只需要修改一下对象的前后指针的指向位置。
所以在系统中如果需要经常在任意位置插入元素，则可以考虑使用LinkedList代替ArrayList。
操作二：在任意位置做删除操作。
在对ArrayList进行删除操作时，由于自身是数组实现的，所以也需要进行数组重组。而LinkedList只需要遍历到对应要删除的对象位置然后修改前后位置的指针指向就好了。
操作三：遍历列表。
我们常用的遍历方式有三种：ForEach操作，迭代器和for循环。书中对这三种方法做了比较，最后发现对ArrayList来说for循环这种随机访问的方式效率最高，这是由于他们实现了RandomAccess接口。迭代器比ForEach的方式效率要高一些。但是对于LinkedList来说，for循环这种随机访问的方式性能非常的差。所以对于ArrayList这些基于数组是实现的来说，在遍历对象时可以优先考虑随机访问，对于LinkedList这种基于链表实现的，随机访问的性能特别差，要遍历的话考虑用迭代的方式去实现。
Part III.Map类型
Map是非常常用的数据结构，下面是从网上找的Map的类图，围绕着Map接口，最主要的实现类有Hashtable、HashMap、LinkedHashMap和treeMap。我们平时用的最多的可能是中间两个。还有我们平时读取配置文件经常用到的properties类也是Map的一种实现。值得我们关注的是，HashMap和Hashtable有两套不同的实现，两者都是实现了Map接口，但不同的是，Hashtable的大部分方法都做了同步，而HashMap没有，所以HashMap不是线程安全的。其次Hashtable不允许key或者value使用null值，而HashMap可以。第三，他们对key的hash算法和hash值到内存索引的映射算法不同。
HashMap的实现原理：
HashMap其实就是将Key做hash算法，然后得到的hash值映射到内存地址，直接取得key所对应的数据。在HashMap中，底层数据结构使用的是数组，内存地址其实就是数组下标索引。HashMap的高性能需要保证以下几点：
■ Hash算法必须是高效的。
■ Hash值到内存地址的算法是快速的
■ 根据内存地址可以直接取到对应的值
下图中就是HashMap中hash计算方法
key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。在取到散列值后还做一个操作就是先右移了16位再和自己异或处理了一下。其实这个处理是有一定的原因的。因为HashMap的put方法里除了调用到了hash()方法外，调用到了putVal方法。在putVal方法里面有个被选中的部分，就是来确定数组下标的（上面说过了HashMap底层其实就是用数组和链表实现的）。因为我们知道HashMap的初始大小是16，但是通过hashCode()返回的散列值的二进制后面几位可能都是0，这个时候直接和n-1（n是整个散列表的长度）按位与的话返回结果可能就是0，如果这样的话，可能很多值都会堆积在散列表索引为0的这个位置，导致效率低下。
举个栗子，我们默认n为16，然后16-1=15，转化为二进制后为1111。此时，假设hash的值不做 h = key.hashCode() ^ (h >>> 16) 这样的处理而是直接调用 h = key.hashCode() 得到h，h的值为10100110101000000，那么1111和h按位与，i 结果就为0 。那么传入的键值对放的位置就是tab[0]位置或者说是在挂tab[0]位置下面的链表的一个节点。这样的话大多数类似于 xxxx xxxx 0000这样的数和 1111 按位与或结果都为0。那么tab[0]位置有可能会存储很多的值，即链表的长度会很长，这样查找时就会降低了性能。
如果我们这个时候做了右移16位然后和自己异或的操作的话，h的值就是00000000000000001，然后再和1111按位与，得到就是00000000000001110，即14。这个时候就不再返回0了。
其实介绍了这么多，就是想说在计算hash值时效率是很高的。
Hash冲突问题，在一些特殊情况下，HashMap还是会遇到一些性能问题，当通过Hash计算后，发现对应的内存中的同一个地址时，就出现了Hash冲突的问题，虽然HashMap底层使用数组实现的，但是数组里的元素不知一个简单值，而是一个Entry对象，每个Entry对象里面包含key，value，next，hash等几项。里面的next是一个指向另外一个Entry的指针。所以当put操作有冲突时，新的Entry依然会被放在其hash值对应的索引下标内，并替换原有的值，同时，为了保证旧值不丢失，会将新的Entry的next指向旧值。这样就实现了一个数组索引空间内存放多个值，其实相当于一个数组项里面存的是一个单向链表。
除了hashcode冲突导致的性能问题，还有个影响HashMap性能的是它的容量参数。和ArrayList和Vector这种基于数组的结构一样，在空间不足时同样需要进行扩展。
HashMap有两个可以指定初始化大小的构造函数，其中一个可以设置一个负载因子，我们以这个函数为例。
initialCapacity指定了HashMap的初始容量，loadFactor指定了其负载因子。一般初始默认情况，初始大小为16，负载因子为0.75.
负载因子=元素个数/内部数组总大小
在HashMap内部还有一个threshold的变量，这个变量值等于当前数组总容量和负载因子的乘积。它表示HashMap的阈值，当HashMap的实际容量超过阈值时，HashMap就会进行扩容。很明显，HashMap的扩容操作会遍历整个HashMap，所以应该设置合理的初始大小和负载因子，以避免扩容操作的发生。
上面我们介绍了HashMap的实现原理和一些需要注意的地方，虽然HashMap有很不错的效率，但是它是无序的，被存入在HashMap的元素，在遍历HashMap时，其输出是无序的。如果希望元素是输出时是按照存入的顺序的话，就需要使用LinkedHashMap来替代。与HashMap不同的是，LinkedHashMap内部增加了一个链表，用于存放元素的顺序。
LinkedHashMap可以提供两种类型的顺序：一种是是元素插入时的顺序，第二种是最近访问的顺序。默认是按插入顺序的，当accessOrder声明为true时，则是按照最近访问顺序。LinkedHashMap继承了HashMap的Entry类，同时还增加了before和after两个属性，用来记录某一个表项的前驱和后继，并构成了循环链表。
TreeMap，支持进行排序的一种Map，他实现了SortedMap接口，可以对元素进行排序。TreeMap是根据元素的Key进行排序的，为了确定Key的排序顺序，可以使用两种方法指定。（1）在TreeMap的构造函数中注入一个Comparator（2）使用一个实现了Comparable接口的Key。使用TreeMap时是必须进行排序操作的，所以使用过程中一定要通过上面两个方式中的其中一种将排序规则递给TreeMap。TreeMap的内部实现是基于红黑树，红黑树是一种平衡查找树。关于红黑树的算法有些复杂，有空再详细了解一下。
如果需要将排序功能假如HashMap时，尽量使用TreeMap而不是本人在程序中实现排序算法。
Part IV.Set接口
Set接口在Collection接口之上没有增加额外的操作，Set集合中的元素是不能重复的。关于Set的实现有HashSet、LinkedHashSet和TreeSet。这三个都是基于上面介绍的对应的Map的一种封装而已，内部的方法都是差不多的。这里就不再重复介绍，只要记住元素不能重复就好了。
