java数据结构分析及优化

谁借莪１个温暖的怀抱￠ 2022-09-30 04:54 178阅读 0赞

转java开发同事整理的java知识点梳理，对偶很有帮助，希望对各位也有所帮助

全文：

使用java很多年了，但一直都是用它做后台，没有做过前台。在java的构架方面，知道很少（如spring, hibernate），但对java如何做后台，还是有比较深刻的理解，对jdk的源码，也做过很多分析。再次把这些和数据结构有关的东西总结一下，算是对多年使用的java的一个敬意吧。

第一点：java基础元素的内存占用

![1288235425\_6.png][1288235425_6.png]

从上面的数据可以明显看出来，java自带复杂数据结构（list, map)等，因为他们采用的都是Object作为模板参数，故占用内存都很严重。如果可以，可以采用gnu的trove库来替换java的库。

参考文献：[http://www.javamex.com/tutorials/memory/string\_memory\_usage.shtml][http_www.javamex.com_tutorials_memory_string_memory_usage.shtml]

第二点：java为啥比较慢

1、java的分配内存

java只把内嵌类型分配到堆栈上面，所有Object类型都分配到堆上面。  
c++可以把局部变量都分配到堆栈上面。  
显然，根据已有测试结果，访问堆栈的速度要远高于堆的速度。

启示1：c++不要返回structure，可以用引用先传入返回对象；  
启示2：java对象不要随便抛弃，尽量延长其生命周期；但并不是说要维持一个对象pool；

2、java没有真正的模板

没有模板的缺点就在于需要进行类型转换。类型转换是一个很耗时的操作。

3、xxx

4、c++的内存占用如何？

tr1自带的hashmap(int,int)，一个占用16字节，是实际数据的2倍；  
stl自带的map(int,int)，一个占用32字节，是实际数据的4倍；  
自己写的话，常见的是1.2倍左右的空间占用。

5、为什么java版本的底层结构效率不佳？

a）java没有数组转对象的功能  
b）java对象内存位置是自动分配，无法控制

参考：[http://www.jelovic.com/articles/why\_java\_is\_slow.htm][http_www.jelovic.com_articles_why_java_is_slow.htm]  
参考：[http://www.idiom.com/~zilla/Computer/javaCbenchmark.html][http_www.idiom.com_zilla_Computer_javaCbenchmark.html]

第三点：java的优化建议

1、rule No1：不要优化代码！

注：必须编写足够可读的代码；

2、rule No2：选定优化目标

注：一般只有20%左右的代码是瓶颈所在

3、通用优化技术

**A、操作符简约**  
注：如把"/=2^n"简化为">>=n"；

**B、公共表达式提取**  
注：  
double x=d\*a\*b;  
double y=e\*a\*b;  
可以修改为：  
c=a\*b;  
x=d\*c;  
y=e\*c; // 后2句在cpu层次可以并行计算

**C、预先计算不变的值**  
如：  
for(int i=0;i<N;i++)  
 x\[i\] = Math.PI\*Math.cos(y)\*i;  
可以修改为：  
double d = Math.PI\*Math.cos(y);  
for(int i=0;i<N;i++)  
 x\[i\] = d\*i;

**D、部分展开循环**  
如：  
for(int i=0;i<N;i++)  
 x\[i\]=i;  
可以修改为：  
for(int i=0;i<N;i+=3)  
\{  
 x\[i\]=i;  
 x\[i+1\]=i+1;  
 x\[i+2\]=i+2;  
\}

**E、try结束循环技术**  
如：  
for(int i=0;i<a.length;i++)  
 a\[i\]=i\*i;  
修改为：  
try\{  
 for(int i=0;;i++)  
  a\[i\]=i\*i;  
\}catch(Exception nouse)  
\{  
\}  
注意：这种技术节约了一次判断，只有在循环次数时很大（过千万）时才有效；

**4、对基本数据结构的说明**

A、数组拷贝，用System.arraycopy  
B、Arrays.sort方法在sort对象数组的时候，采用的是稳定的归并排序  
C、Arrays.sort方法在sort内嵌类型数组的时候，采用的不是introsort，不要希望它有stl::sort的速度  
D、Collections.sort方法会先把List拷贝成Array，然后调用Arrays.sort，速度很慢  
E、ArrayList的自增长比例是1.5，即每次不够了自动增长50%(+1)  
F、BitSet内部使用long数组来实现，在32位机器上面的速度不高  
G、HashMap的默认填充率是0.75  
H、PriorityQueue虽然是最小堆的数值实现，但其速度很慢，量大的时候，不如TreeMap  
I、Vector和ArrayList都不能用作需要删除操作的数组，如果需要，建议自己实现，可以采用延迟删除策略  
J、Map和HashMap都和c++的stl::map和stl::hashtable实现算法一样  
K、StringBuilder和StringBuffer的不同点在于后者可以多线程调用（自然速度就更慢）  
L、注意String著名的内存泄露问题！对于原始字符串很长时一定注意不要随便调用substring方法，应该直接拷贝

**5、对正则表达式的说明**

A、千万注意String.split方法，它的效率特别低，每次都需要编译表达式！  
B、不要使用：  
 X+  
   修改为：  
   X\{1,1024\}  
   原因在于前者在输入为1000个X的时候，会导致堆栈（即函数调用）有1000多层，内存不足；

**6、选用最新的jvm和采用-server选项**

注：只有采用-server选项后，jvm才会预先编译（否则就看hotspot的心情了）

**误区：**

1、方法必须加final，并且不能使用任何非final的局部变量，才能被inline  
注：所有的方法都能被inline（虽然Jvm可能选择不inline）

2、类必须加上final，才能够让方法可能被inline  
注：hotspot的好处就在于它有deoptimize的能力，在检测到方法不应该被inline时，它能够自我更正，重新inline  
注：当然了，如果可以加上final，避免hotspot额外工作。

参考文献：[http://java.sun.com/products/hotspot/docs/general/hs2.html][http_java.sun.com_products_hotspot_docs_general_hs2.html]  
参考文献：[http://lotusroots.bokee.com/5886635.html][http_lotusroots.bokee.com_5886635.html]

[1288235425_6.png]: 
[http_www.javamex.com_tutorials_memory_string_memory_usage.shtml]: http://www.javamex.com/tutorials/memory/string_memory_usage.shtml
[http_www.jelovic.com_articles_why_java_is_slow.htm]: http://www.jelovic.com/articles/why_java_is_slow.htm
[http_www.idiom.com_zilla_Computer_javaCbenchmark.html]: http://www.idiom.com/~zilla/Computer/javaCbenchmark.html
[http_java.sun.com_products_hotspot_docs_general_hs2.html]: http://java.sun.com/products/hotspot/docs/general/hs2.html
[http_lotusroots.bokee.com_5886635.html]: http://lotusroots.bokee.com/5886635.html