网站如何运营,免费网站空间 评测,建设厅网站合同备案在哪里,网站规划和建设的步骤小夕在本系列前两篇文章中为大家介绍了各类数据结构的扩容策略#xff0c;且在上篇文末#xff0c;小夕提到了加倍式扩容中#xff0c;倍率采用2并不是最优的#xff0c;为什么呢#xff1f;有没有最优倍率呢#xff1f;内存复用如果倍率采用2甚至更大的数#xff0c;那… 小夕在本系列前两篇文章中为大家介绍了各类数据结构的扩容策略且在上篇文末小夕提到了加倍式扩容中倍率采用2并不是最优的为什么呢有没有最优倍率呢 内存复用如果倍率采用2甚至更大的数那么被开辟过的旧空间永远都不会被新开辟的空间利用。小夕举个栗子。 if(倍率≥2){那么以下是小夕为大家画的三次扩容后的内存块的占用情况小夕用PPT画的好麻烦的喵读者喵有好用的轻量级画矢量图的软件记得推荐给小夕哦~ 上图中内存块一共有15个字节。粉色实心框是数据结构占用的内存块空心框是空闲的内存。 假如一开始数据结构的大小是1字节占用了0xFF00这个字节如图中第一列。然后第一次扩容后数据结构大小变成2字节无法利用之前的旧内存空间。同样第二次扩容第三次扩容后数据结构的大小总是要比之前累计占用的旧内存空间之和还要大总是大1个字节所以永远都无法重新利用之前的旧内存空间。 那么无法复用旧内存空间对应有程序与操作系统各有什么影响呢小夕还没有探索出严谨的结论读者有思路可以跟小夕一起讨论哦~ 如果倍率改为比2大的数结果是一样的。有兴趣的喵喵可以自行画画图~当然数学好的喵喵不用画图也能证明出来的~利用几何级数的性质} if(倍率2倍率1){比如倍率采用1.5。小夕再画一下图~ 可以看到第三次扩容后的新数据结构大小约为338B而旧空间的大小是250225475338也就是说新的哈希表可以挪到旧的内存空间了内存得到了复用 好咯说到这里读者应该懂了对于加倍式扩容倍率必须小于2才能复用内存。那么为什么默认值取1.5而不是1.61.7呢小夕查了很多资料发现这是一个启发式策略启发式策略就是拍脑袋想出来的看似合理而没有严谨理论依据的方法。 一个疑问 那么既然看似倍率用1.5要优于2为什么Java中的哈希表系列以及C中的Vector却采用2呢 这就是理论与工程的不同之处。在工程中不仅要考虑内存复用这一个问题还要考虑到浮点数运算问题和大量数据场景下的扩容速度的问题。 具体来说若采用1.5倍那么假设数据结构初始大小为10则以后的数据结构大小会依次计算为15,22.5,33.75,50.625,75.9375... 可以看到浮点运算的代价会越来越高。 扩容速度也很好理解。大量数据时2倍扩容速度会比1.5倍扩容速度少很多次扩容次数因此效率会比1.5倍高很多。那么当程序不怎么看重内存复用却有大量数据待填入数据结构时2倍是更合理的。 So虽然很多数据结构都是基于静态数组实现的动态空间增长但是有的是上述提到的2倍的扩容倍率有的像Java中的ArrayList则为1.5倍的扩容倍率。 看来如何决定倍率要在设计数据结构的时候好好考虑这个数据结构将来的业务场景呢。PS没有发现小夕在上面的一个if语句中漏了一半括号的C/C/Java等程序员请自觉面壁思过。 最后不知道您对小夕的文章是否满意呢(⁎⁍̴̛ᴗ⁍̴̛⁎)小夕已委托维权骑士对小夕发布文章的版权行为进行追究与维权。欢迎大家转发分享~如需转载请联系微信xiyaomengmengda。
