数组、字符串类问题小记

数组、字符串类的问题，是一类最为基础的问题，但是比较考察人，也经常出现在技术面中，今天想就这类问题，做个记录，好记心不如烂笔头。

也欢迎大神们补充、纠正。

关于字符串的问题，就我见过的，大部分集中在字符串查找、匹配、拆分、拼接这些方面。大部分的字符串问题，都可以用数组解决。或者说数组常用的手段之一。

在Java里，数组相关的有哪些结构，

常见的arrayList是典型的动态数组，需要注意的是，它每次扩容，都要扩为原来的1.5倍，记得1.6中扩容方式是 old*3/2+1，而1.7之后，变成了移位操作(也可以看出，cpu级别的指令操作，对性能的提升是很有帮助的)：

然后会将元素全部复制，比较耗性能，所以，在使用时，如果可以确定元素个数，最好指定容量，避免扩容时的性能和空间的损耗。

还有HashMap也可以看成是数组结构，是一个Entry数组。初始化大小16，装填因子是0.75 ,需要注意的是，hashMap,采用的是链式冲突解决，

如果hash算法选择的不好，就会出现，元素总是挂在e.next()后面，但是容量总是不够0.75的糟糕情况。

在字符串拼接方面性能较优的是Stringbuffer 和StringBuilder,区别在于线程安全。是因为，其内部采用了char型变长数组，可以将字符全部加入之后，在一次性转为String；而采用String的直接拼接方式，时间复杂度将是糟糕的O(n方)：

比如N个等长为n的String直接拼接，复制操作将是n+2n+3n+...+n*N，等差数列，其和是n*N(1+N)/2(如果我没有记错的话)，所以，复杂度是N方的。

而在字符串拆分方面，String的split方法的性能是不好的，因为它采用的是正则匹配。遇到这种情况，甚至可以自己实现一个拆分算法，来满足自己对拆分性能的要求，比如kmp; Java中的StringTokenizer类也是一个比较高效的拆分方法类。

只有我们把这些数据结构的运用细化到每一次扩容、填充，才能为高效的解决问题奠定好的基础。