模拟指针可以做什么

说实话这乱七八糟一堆文字我看了两边,然后发现真救不了你. ######回复 @刘子玄:操作系统不管理寄存器，现在都是抢占式多线程操作系统，都是在线程释放资源的时候切换到其他进程的(你调用某些api的时候会发生等待和切换操作,然后保存线程执行环境数据)看一下操作系统原理的书籍就知道了.直接切换那个只有纯正的分时操作系统才会去做.现在估计只剩下大型UNIX了######==######靠时钟中断，硬件一定会定时发起时钟中断，中断服务一定会执行，这样就可以进行调度或做其他事了，中断机制由硬件保证。找书看吧，这些问题不是几句说得清。######谢了######在中断产生时，寄存器压栈，在中断结束后，堆栈的数据弹回到寄存器。###### 寄存器操作是汇编级别的最小操作单元,即使是操作系统也不能够管理寄存器. 是计算机有一些指令,能够自己把所有寄存器保存到一个地方.######计算机基础如此博大精深，几十年高科技结晶，不是三天三夜就能说清的，更何况几句话###### 简单2个字压栈.OS的原理很简单,你可以找一些嵌入式的OS开源代码进行阅读,相信读完2个系统的代码后,就对OS核心部分很清楚了. 挑你的一个问题进行回答:" 操作系统是如何让一个程序在规定时间内执行再准确的暂停了？这是如何控制的？"      感觉你还不清楚调度算法的实现.简单的说:硬件中断将其打断,如果需要1ms的进程调度精度,那么就设置时钟中断为1ms. 你可以看下中断部分的代码.       CPU的PC指针即使软件不去设置它也不是固定不变只能向下跑的.当中断发生的时候,PC指针会自动修改到相应中断向量的物理地址上,并且中断时的重要寄存器的值被硬件自动保存. 于是我们就设置一个时钟中断向量(将这个地址上写入我们的代码函数的地址),每18msPC指针会被自动改到这个地方,在这个地方我们根据调度算法,看是继续执行被打断的线程还是切换到更合适的线程上.  感性上,线程/cpu的运行实际上是非常的不连贯, 中途不断的被各种中断疯狂的打断.尤其高响应的硬实时OS,打断应该更加频繁. 我们想干任何事情都可以在中断处理中去做.        此外除了硬件中断,因为硬件功能都是api提供,so程序代码实际上经常会很频繁调用一些系统API,既然调用了系统api,os也完全可以在系统api执行软中断,执行调度算法,把pc指针移到别处去,不再正常的函数返回了(保存好数据,下次调度它时,模拟这个函数返回,应用程序完全不知道发生了什么). ######一个嵌入式OS的代码不过几千行而已. 看完几个 你就精通OS的实现了.不过"知识改变命运", 懂得越多混得越惨, 个人建议你干点其他能赚钱的事情.底层实现的东西,除了吹牛,提升点技术素质,对赚钱来说毫无用处,面试时都没用!!(实际上现在面试都是看算法)  小正太, 根据赚钱来指导自己学习/背诵什么东西.(很心痛的经验)######回复 @MinGKai:haha.反正比赚1个亿简单多了.######“精通”OS有那么简单么…………######这个你放心，我只会把编程当成毕生的爱好，而不会用作工作。

说实话这乱七八糟一堆文字我看了两边,然后发现真救不了你. ######回复 @刘子玄 : 操作系统不管理寄存器，现在都是抢占式多线程操作系统，都是在线程释放资源的时候切换到其他进程的(你调用某些api的时候会发生等待和切换操作,然后保存线程执行环境数据)看一下操作系统原理的书籍就知道了.直接切换那个只有纯正的分时操作系统才会去做.现在估计只剩下大型UNIX了######= =######靠时钟中断，硬件一定会定时发起时钟中断，中断服务一定会执行，这样就可以进行调度或做其他事了，中断机制由硬件保证。找书看吧，这些问题不是几句说得清。######谢了######在中断产生时，寄存器压栈，在中断结束后，堆栈的数据弹回到寄存器。###### 寄存器操作是汇编级别的最小操作单元,即使是操作系统也不能够管理寄存器. 是计算机有一些指令,能够自己把所有寄存器保存到一个地方. ######计算机基础如此博大精深，几十年高科技结晶，不是三天三夜就能说清的，更何况几句话###### 简单2个字 压栈. OS的原理很简单, 你可以找一些嵌入式的OS开源代码进行阅读, 相信读完2个系统的代码后, 就对OS核心部分很清楚了. 挑你的一个问题进行回答: "操作系统是如何让一个程序在规定时间内执行再准确的暂停了？这是如何控制的？"       感觉你还不清楚调度算法的实现.简单的说: 硬件中断将其打断,如果需要1ms的进程调度精度,那么就设置时钟中断为1ms.  你可以看下中断部分的代码.        CPU的PC指针即使软件不去设置它也不是固定不变只能向下跑的. 当中断发生的时候,PC指针会自动修改到相应中断向量的物理地址上,并且中断时的重要寄存器的值被硬件自动保存.  于是我们就设置一个时钟中断向量(将这个地址上写入我们的代码函数的地址), 每18ms PC指针会被自动改到这个地方,在这个地方 我们根据调度算法, 看是继续执行被打断的线程 还是切换到更合适的线程上.   感性上, 线程/cpu 的运行 实际上是非常的不连贯,  中途不断的被各种中断疯狂的打断. 尤其高响应的硬实时OS,打断应该更加频繁.  我们想干任何事情都可以在中断处理中去做.         此外除了硬件中断, 因为硬件功能都是api提供,so程序代码实际上经常会很频繁调用一些系统API, 既然调用了系统api, os也完全可以在系统api执行软中断, 执行调度算法, 把pc指针移到别处去, 不再正常的函数返回了(保存好数据, 下次调度它时,模拟这个函数返回, 应用程序完全不知道发生了什么). ######一个嵌入式OS的代码不过几千行而已.  看完几个  你就精通OS的实现了. 不过"知识改变命运",  懂得越多混得越惨,  个人建议你干点其他能赚钱的事情. 底层实现的东西, 除了吹牛, 提升点技术素质, 对赚钱来说毫无用处, 面试时都没用!! (实际上现在面试都是看算法)   小正太,  根据赚钱来指导自己学习/背诵 什么东西. (很心痛的经验)######回复 @MinGKai : haha. 反正比赚1个亿简单多了.######“精通”OS有那么简单么…………######这个你放心，我只会把编程当成毕生的爱好，而不会用作工作。

在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结构，但是在jdk1.8里 加入了红黑树的实现，当链表的长度大于8时，转换为红黑树的结构。这里写图片描述从上图中可以看出，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。 */ static class Node<K,V> implements Map.Entry<K,V> { final int hash;//用于定位数组索引的位置 final K key; V value; Node<K,V> next;//链表的下一个Node Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法

关于二十四点游戏的编程思路与基本算法 漫长的假期对于我来说总是枯燥无味的，闲来无聊便和同学玩起童年时经常玩的二十四点牌游戏来。此游戏说来简单，就是利用加减乘除以及括号将给出的四张牌组成一个值为24的表达式。但是其中却不乏一些有趣的题目，这不，我们刚玩了一会儿，便遇到了一个难题——3、6、6、10（其实后来想想，这也不算是个太难的题，只是当时我们的脑筋都没有转弯而已，呵呵）。 问题既然出现了，我们当然要解决。冥思苦想之际，我的脑中掠过一丝念头——何不编个程序来解决这个问题呢。文曲星中不就有这样的程序吗。所以这个想法应该是可行。想到这里我立刻开始思索这个程序的算法，最先想到的自然是穷举法（后来发现我再也想不到更好的方法了，悲哀呀，呵呵），因为在这学期我曾经写过一个小程序——计算有括号的简单表达式。只要我能编程实现四个数加上运算符号所构成的表达式的穷举，不就可以利用这个计算程序来完成这个计算二十四点的程序吗。确定了这个思路之后，我开始想这个问题的细节。 首先穷举的可行性问题。我把表达式如下分成三类—— 1、 无括号的简单表达式。 2、 有一个括号的简单表达式。 3、 有两个括号的较复4、 杂表达式。 穷举的开始我对给出的四个数进行排列，其可能的种数为4*3*2*1=24。我利用一个嵌套函数实现四个数的排列，算法如下: /* ans[] 用来存放各种排列组合的数组 */ /* c[] 存放四张牌的数组 */ /* k[] c[]种四张牌的代号，其中k[I]=I+1。 用它来代替c[]做处理，考虑到c[]中有可能出现相同数的情况 */ /* kans[] 暂存生成的排列组合 */ /* j 嵌套循环的次数 */ int fans(c,k,ans,kans,j) int j,k[],c[];char ans[],kans[]; { int i,p,q,r,h,flag,s[4],t[4][4]; for(p=0,q=0;p<4;p++) { for(r=0,flag=0;r if(k[p]!=kans[r]) flag++; if(flag==j) t[j][q++]=k[p]; } for(s[j]=0;s[j]<4-j;s[j]++) { kans[j]=t[j][s[j>; if(j==3) { for(h=0;h<4;h++) ans[2*h]=c[kans[h]-1]; /* 调整生成的排列组合在最终的表 达式中的位置 */ for(h=0;h<3;h++) symbol(ans,h); /* 在表达式中添加运算符号 */ } else { j++; fans(c,k,ans,kans,j); j--; } } } 正如上面函数中提到的，在完成四张牌的排列之后，在表达式中添加运算符号。由于只有四张牌，所以只要添加三个运算符号就可以了。由于每一个运算符号可重复，所以计算出其可能的种数为4*4*4=64种。仍然利用嵌套函数实现添加运算符号的穷举，算法如下: /* ans[],j同上。sy[]存放四个运算符号。h为表达式形式。*/ int sans(ans,sy,j,h) char ans[],sy[];int j,h; { int i,p,k[3],m,n; char ktans[20]; for(k[j]=0;k[j]<4;k[j]++) { ans[2*j+1]=sy[k[j>; /* 刚才的四个数分别存放在0、2、4、6位 这里的三个运算符号分别存放在1、3、5位*/ if(j==2) { ans[5]=sy[k[j>; /* 此处根据不同的表达式形式再进行相应的处理 */ } else } } 好了，接下来我再考虑不同表达式的处理。刚才我已经将表达式分为三类，是因为添加三个括号对于四张牌来说肯定是重复的。对于第一种，无括号自然不用另行处理；而第二种情况由以下代码可以得出其可能性有六种，其中还有一种是多余的。 for(m=0;m<=4;m+=2) for(n=m+4;n<=8;n+=2) 这个for循环给出了添加一个括号的可能性的种数，其中m、n分别为添加在表达式中的左右括号的位置。我所说的多余的是指m=0，n=8，也就是放在表达式的两端。这真是多此一举，呵呵。最后一种情况是添加两个括号，我分析了一下，发现只可能是这种形式才不会是重复的——（a b）(c d)。为什么不会出现嵌套括号的情况呢。因为如果是嵌套括号，那么外面的括号肯定是包含三个数字的（四个没有必要），也就是说这个括号里面包含了两个运算符号，而这两个运算符号是被另外一个括号隔开的。那么如果这两个运算符号是同一优先级的，则肯定可以通过一些转换去掉括号（你不妨举一些例子来试试），也就是说这一个括号没有必要；如果这两个运算符号不是同一优先级，也必然是这种形式((a+-b)*/c)。而*和/在这几个运算符号中优先级最高，自然就没有必要在它的外面添加括号了。 综上所述，所有可能的表达式的种数为24*64*（1+6+1）=12288种。哈哈，只有一万多种可能性（这其中还有重复），这对于电脑来说可是小case哟。所以，对于穷举的可行性分析和实现也就完成了。 接下来的问题就是如何对有符号的简单表达式进行处理。这是栈的一个著名应用，那么什么是栈呢。栈的概念是从日常生活中货物在货栈种的存取过程抽象出来的，即最后存放入栈的货物（堆在靠出口处）先被提取出去，符合“先进后出，后进先出”的原则。这种结构犹如子弹夹。 在栈中，元素的插入称为压入（push）或入栈，元素的删除称为弹出（pop）或退栈。 栈的基本运算有三种，其中包括入栈运算、退栈运算以及读栈顶元素，这些请参考相关数据结构资料。根据这些基本运算就可以用数组模拟出栈来。 那么作为栈的著名应用，表达式的计算可以有两种方法。 第一种方法—— 首先建立两个栈，操作数栈OVS和运算符栈OPS。其中，操作数栈用来记忆表达式中的操作数，其栈顶指针为topv，初始时为空，即topv=0；运算符栈用来记忆表达式中的运算符，其栈顶指针为topp，初始时，栈中只有一个表达式结束符，即topp=1，且OPS（1）=‘；’。此处的‘；’即表达式结束符。 然后自左至右的扫描待处理的表达式，并假设当前扫描到的符号为W，根据不同的符号W做如下不同的处理： 1、 若W为操作数 2、 则将W压入操作数栈OVS 3、 且继续扫描下一个字符 4、 若W为运算符 5、 则根据运算符的性质做相应的处理： (1)、若运算符为左括号或者运算符的优先级大于运算符栈栈顶的运算符(即OPS(top)),则将运算符W压入运算符栈OPS，并继续扫描下一个字符。 (2)、若运算符W为表达式结束符‘；’且运算符栈栈顶的运算符也为表达式结束符（即OPS(topp)=’;’），则处理过程结束，此时，操作数栈栈顶元素（即OVS（topv））即为表达式的值。 (3)、若运算符W为右括号且运算符栈栈顶的运算符为左括号（即OPS（topp）=’(‘)，则将左括号从运算符栈谈出，且继续扫描下一个符号。 (4)、若运算符的右不大于运算符栈栈顶的运算符（即OPS(topp)），则从操作数栈OVS中弹出两个操作数，设先后弹出的操作数为a、b，再从运算符栈OPS中弹出一个运算符，设为+，然后作运算a+b,并将运算结果压入操作数栈OVS。本次的运算符下次将重新考虑。 第二种方法—— 首先对表达式进行线性化，然后将线性表达式转换成机器指令序列以便进行求值。 那么什么是表达式的线性化呢。人们所习惯的表达式的表达方法称为中缀表示。中缀表示的特点是运算符位于运算对象的中间。但这种表示方式，有时必须借助括号才能将运算顺序表达清楚，而且处理也比较复杂。 1929年，波兰逻辑学家Lukasiewicz提出一种不用括号的逻辑符号体系，后来人们称之为波兰表示法（Polish notation）。波兰表达式的特点是运算符位于运算对象的后面，因此称为后缀表示。在对波兰表达式进行运算，严格按照自左至右的顺序进行。下面给出一些表达式及其相应的波兰表达式。 表达式 波兰表达式 A-B AB- （A-B）*C+D AB-C*D+ A*（B+C/D）-E*F ABCD/+*EF*- （B+C）/（A-D） BC+AD-/ OK，所谓表达式的线性化是指将中缀表达的表达式转化为波兰表达式。对于每一个表达式，利用栈可以把表达式变换成波兰表达式，也可以利用栈来计算波兰表达式的值。 至于转换和计算的过程和第一种方法大同小异，这里就不再赘述了。 下面给出转换和计算的具体实现程序—— /* first函数给出各个运算符的优先级，其中=为表达式结束符 */ int first(char c) { int p; switch(c) { case '*': p=2; break; case '/': p=2; break; case '+': p=1; break; case '-': p=1; break; case '(': p=0; break; case '=': p=-1; break; } return(p); } /* 此函数实现中缀到后缀的转换 */ /* M的值宏定义为20 */ /* sp[]为表达式数组 */ int mid_last() { int i=0,j=0; char c,sm[M]; c=s[0]; sm[0]='='; top=0; while(c!='\0') { if(islower(c)) sp[j++]=c; else switch(c) { case '+': case '-': case '*': case '/': while(first(c)<=first(sm[top])) sp[j++]=sm[top--]; sm[++top]=c; break; case '(': sm[++top]=c; break; case ')': while(sm[top]!='(') sp[j++]=sm[top--]; top--; break; default :return(1); } c=s[++i]; } while(top>0) sp[j++]=sm[top--]; sp[j]='\0'; return(0); } /* 由后缀表达式来计算表达式的值 */ int calc() { int i=0,sm[M],tr; char c; c=sp[0]; top=-1; while(c!='\0') { if(islower(c)) sm[++top]=ver[c-'a'];/*在转换过程中用abcd等来代替数， 这样才可以更方便的处理非一位数， ver数组中存放着这些字母所代替的数*/ else switch(c) { case '+': tr=sm[top--]; sm[top]+=tr; break; case '-': tr=sm[top--]; sm[top]-=tr; break; case '*': tr=sm[top--]; sm[top]*=tr; break; case '/': tr=sm[top--];sm[top]/=tr;break; default : return(1); } c=sp[++i]; } if(top>0) return(1); else } 这样这个程序基本上就算解决了，回过头来拿这个程序来算一算文章开始的那个问题。哈哈，算出来了，原来如此简单——（6-3）*10-6=24。 最后我总结了一下这其中容易出错的地方—— 1、 排列的时候由于一个数只能出现一次， 所以必然有一个判断语句。但是用什么来判断，用大小显然不行，因为有可能这四个数中有两个或者以上的数是相同的。我的方法是给每一个数设置一个代号，在排列结束时，通过这个代号找到这个数。 2、在应用嵌套函数时，需仔细分析程序的执行过程，并对个别变量进行适当的调整（如j的值）,程序才能正确的执行。 3、在分析括号问题的时候要认真仔细，不要错过任何一个可能的机会，也要尽量使程序变得简单一些。不过我的分析可能也有问题，还请高手指点。 4、在用函数对一个数组进行处理的时候，一定要注意如果这个数组还需要再应用，就必须将它先保存起来，否则会出错，而且是很严重的错误。 5、在处理用户输入的表达式时，由于一个十位数或者更高位数是被分解成各位数存放在数组中，所以需对它们进行处理，将它们转化成实际的整型变量。另外，在转化过程中，用一个字母来代替这个数，并将这个数存在一个数组中，且它在数组中的位置和代替它的这个字母有一定的联系，这样才能取回这个数。 6、由于在穷举过程难免会出现计算过程中有除以0的计算，所以我们必须对calc函数种对于除的运算加以处理，否则程序会因为出错而退出（Divide by 0）。 7、最后一个问题，本程序尚未解决。对于一些比较著名的题目，本程序无法解答。比如说5、5、5、1或者8、8、3、3。这是由于这些题目在计算的过程用到了小数，而本程序并没有考虑到小数。

遍历一个 List 有哪些不同的方式？每种方法的实现原理是什么？Java 中 List 遍历的最佳实践是什么？ 遍历方式有以下几种： for 循环遍历，基于计数器。在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后停止。 迭代器遍历，Iterator。Iterator 是面向对象的一个设计模式，目的是屏蔽不同数据集合的特点，统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。 foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现，使用时不需要显式声明 Iterator 或计数器。优点是代码简洁，不易出错；缺点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。 最佳实践：Java Collections 框架中提供了一个 RandomAccess 接口，用来标记 List 实现是否支持 Random Access。 如果一个数据集合实现了该接口，就意味着它支持 Random Access，按位置读取元素的平均时间复杂度为 O(1)，如ArrayList。如果没有实现该接口，表示不支持 Random Access，如LinkedList。 推荐的做法就是，支持 Random Access 的列表可用 for 循环遍历，否则建议用 Iterator 或 foreach 遍历。 说一下 ArrayList 的优缺点 ArrayList的优点如下： ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了 RandomAccess 接口，因此查找的时候非常快。ArrayList 在顺序添加一个元素的时候非常方便。 ArrayList 的缺点如下： 删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。插入元素的时候，也需要做一次元素复制操作，缺点同上。 ArrayList 比较适合顺序添加、随机访问的场景。 如何实现数组和 List 之间的转换？ 数组转 List：使用 Arrays. asList(array) 进行转换。List 转数组：使用 List 自带的 toArray() 方法。 代码示例： ArrayList 和 LinkedList 的区别是什么？ 数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全； 综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。 补充：数据结构基础之双向链表 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。 ArrayList 和 Vector 的区别是什么？ 这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合 线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。性能：ArrayList 在性能方面要优于 Vector。扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在 Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。 Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。 Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。 插入数据时，ArrayList、LinkedList、Vector谁速度较快？阐述 ArrayList、Vector、LinkedList 的存储性能和特性？ ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。 Vector 中的方法由于加了 synchronized 修饰，因此 Vector 是线程安全容器，但性能上较ArrayList差。 LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但插入数据时只需要记录当前项的前后项即可，所以 LinkedList 插入速度较快。 多线程场景下如何使用 ArrayList？ ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样： 为什么 ArrayList 的 elementData 加上 transient 修饰？ ArrayList 中的数组定义如下： private transient Object[] elementData; 再看一下 ArrayList 的定义： public class ArrayList extends AbstractList implements List<E>, RandomAccess, Cloneable, java.io.Serializable 可以看到 ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化，重写了 writeObject 实现： 每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍历 elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大小。 List 和 Set 的区别 List , Set 都是继承自Collection 接口 List 特点：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。 Set 特点：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。 另外 List 支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。 Set和List对比 Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。 List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变 Set接口 说一下 HashSet 的实现原理？ HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，HashMap的value统一为PRESENT，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，HashSet 不允许重复的值。 HashSet如何检查重复？HashSet是如何保证数据不可重复的？ 向HashSet 中add ()元素时，判断元素是否存在的依据，不仅要比较hash值，同时还要结合equles 方法比较。 HashSet 中的add ()方法会使用HashMap 的put()方法。 HashMap 的 key 是唯一的，由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key，并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V。所以不会重复（ HashMap 比较key是否相等是先比较hashcode 再比较equals ）。 以下是HashSet 部分源码： hashCode（）与equals（）的相关规定： 如果两个对象相等，则hashcode一定也是相同的 两个对象相等,对两个equals方法返回true 两个对象有相同的hashcode值，它们也不一定是相等的 综上，equals方法被覆盖过，则hashCode方法也必须被覆盖 hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。 ** ==与equals的区别** ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同 ==是指对内存地址进行比较 equals()是对字符串的内容进行比较3.==指引用是否相同 equals()指的是值是否相同 HashSet与HashMap的区别 Queue BlockingQueue是什么？ Java.util.concurrent.BlockingQueue是一个队列，在进行检索或移除一个元素的时候，它会等待队列变为非空；当在添加一个元素时，它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分，主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间，或消费者有可用的对象，因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现，比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。 在 Queue 中 poll()和 remove()有什么区别？ 相同点：都是返回第一个元素，并在队列中删除返回的对象。 不同点：如果没有元素 poll()会返回 null，而 remove()会直接抛出 NoSuchElementException 异常。 代码示例： Queue queue = new LinkedList (); queue. offer("string"); // add System. out. println(queue. poll()); System. out. println(queue. remove()); System. out. println(queue. size()); Map接口 说一下 HashMap 的实现原理？ HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 HashMap的数据结构： 在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。 HashMap 基于 Hash 算法实现的 当我们往Hashmap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value放入链表中获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。 需要注意Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个之后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn) HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底层实现 在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做拉链法的方式可以解决哈希冲突。 JDK1.8之前 JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。 JDK1.8之后 相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。 JDK1.7 VS JDK1.8 比较 JDK1.8主要解决或优化了一下问题： resize 扩容优化引入了红黑树，目的是避免单条链表过长而影响查询效率，红黑树算法请参考解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。 HashMap的put方法的具体流程？ 当我们put的时候，首先计算 key的hash值，这里调用了 hash方法，hash方法实际是让key.hashCode()与key.hashCode()>>>16进行异或操作，高16bit补0，一个数和0异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为bucket数组大小是2的幂，计算下标index = (table.length - 1) & hash，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。 putVal方法执行流程图 ①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容； ②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③； ③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals； ④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤； ⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可； ⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。 HashMap的扩容操作是怎么实现的？ ①.在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容； ②.每次扩展的时候，都是扩展2倍； ③.扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。 在putVal()中，我们看到在这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上 HashMap是怎么解决哈希冲突的？ 答：在解决这个问题之前，我们首先需要知道什么是哈希冲突，而在了解哈希冲突之前我们还要知道什么是哈希才行； 什么是哈希？ Hash，一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）；这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 所有散列函数都有如下一个基本特性**：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同**。 什么是哈希冲突？ 当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。 HashMap的数据结构 在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突： 这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下，但相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表，所以我们还需要对hashCode作一定的优化 hash()函数 上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下： static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或） } 这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）； JDK1.8新增红黑树 通过上面的链地址法（使用散列表）和扰动函数我们成功让我们的数据分布更平均，哈希碰撞减少，但是当我们的HashMap中存在大量数据时，加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)； 总结 简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的： 使用链地址法（使用散列表）来链接拥有相同hash值的数据；使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；引入红黑树进一步降低遍历的时间复杂度，使得遍历更快； **能否使用任何类作为 Map 的 key？ **可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点： 如果类重写了 equals() 方法，也应该重写 hashCode() 方法。 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。 如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。 用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。 为什么HashMap中String、Integer这样的包装类适合作为K？ 答：String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率 都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况 内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范（不清楚可以去上面看看putValue的过程），不容易出现Hash值计算错误的情况； 如果使用Object作为HashMap的Key，应该怎么办呢？ 答：重写hashCode()和equals()方法 重写hashCode()是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞； 重写equals()方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性； HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标 答：hashCode()方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置； 那怎么解决呢？ HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均； 在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题； HashMap 的长度为什么是2的幂次方 为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。 这个算法应该如何设计呢？ 我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。 那为什么是两次扰动呢？ 答：这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的； HashMap 与 HashTable 有什么区别？ 线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）； 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它； 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。 **初始容量大小和每次扩充容量大小的不同 **： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小，后面会介绍到为什么是2的幂次方。 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。 推荐使用：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。 如何决定使用 HashMap 还是 TreeMap？ 对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。 HashMap 和 ConcurrentHashMap 的区别 ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护，相对于HashTable的synchronized锁的粒度更精细了一些，并发性能更好，而HashMap没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。） HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。 ConcurrentHashMap 和 Hashtable 的区别？ ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。 底层数据结构： JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的； 实现线程安全的方式（重要）： ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。 两者的对比图： HashTable: JDK1.7的ConcurrentHashMap： JDK1.8的ConcurrentHashMap（TreeBin: 红黑二叉树节点 Node: 链表节点）： 答：ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步，HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。 ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？ JDK1.7 首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。 在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式进行实现，结构如下： 一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。 该类包含两个静态内部类 HashEntry 和 Segment ；前者用来封装映射表的键值对，后者用来充当锁的角色；Segment 是一种可重入的锁 ReentrantLock，每个 Segment 守护一个HashEntry 数组里得元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁。 JDK1.8 在JDK1.8中，放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。 结构如下： 如果该节点是TreeBin类型的节点，说明是红黑树结构，则通过putTreeVal方法往红黑树中插入节点；如果binCount不为0，说明put操作对数据产生了影响，如果当前链表的个数达到8个，则通过treeifyBin方法转化为红黑树，如果oldVal不为空，说明是一次更新操作，没有对元素个数产生影响，则直接返回旧值；如果插入的是一个新节点，则执行addCount()方法尝试更新元素个数baseCount； 辅助工具类 Array 和 ArrayList 有何区别？ Array 可以存储基本数据类型和对象，ArrayList 只能存储对象。Array 是指定固定大小的，而 ArrayList 大小是自动扩展的。Array 内置方法没有 ArrayList 多，比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。 对于基本类型数据，集合使用自动装箱来减少编码工作量。但是，当处理固定大小的基本数据类型的时候，这种方式相对比较慢。 如何实现 Array 和 List 之间的转换？ Array 转 List： Arrays. asList(array) ；List 转 Array：List 的 toArray() 方法。 comparable 和 comparator的区别？ comparable接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序comparator接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序 一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo方法或compare方法，当我们需要对某一个集合实现两种排序方式，比如一个song对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的Collections.sort(). 方法如何比较元素？ TreeSet 要求存放的对象所属的类必须实现 Comparable 接口，该接口提供了比较元素的 compareTo()方法，当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。 Collections 工具类的 sort 方法有两种重载的形式， 第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较； 第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator 接口的子类型（需要重写 compare 方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java 中对函数式编程的支持）。

触及 multiple inheritance (MI)（多继承）的时候，C++ 社区就会鲜明地分裂为两个基本的阵营。一个阵营认为如果 single inheritance (SI)（单继承）是有好处的，multiple inheritance（多继承）一定更有好处。另一个阵营认为 single inheritance（单继承）有好处，但是多继承引起的麻烦使它得不偿失。在本文中，我们的主要目的是理解在 MI 问题上的这两种看法。 　　首要的事情之一是要承认当将 MI 引入设计领域时，就有可能从多于一个的 base class（基类）中继承相同的名字（例如，函数，typedef，等等）。这就为歧义性提供了新的时机。例如： class BorrowableItem { // something a library lets you borrowpublic:　void checkOut(); // check the item out from the library　..}; class ElectronicGadget {private:　bool checkOut() const; // perform self-test, return whether　... // test succeeds}; class MP3Player: // note MI herepublic BorrowableItem, // (some libraries loan MP3 players)public ElectronicGadget{ ... }; // class definition is unimportant MP3Player mp; mp.checkOut(); // ambiguous! which checkOut? 　 　注意这个例子，即使两个函数中只有一个是可访问的，对 checkOut 的调用也是有歧义的。（checkOut 在 BorrowableItem 中是 public（公有）的，但在 ElectronicGadget 中是 private（私有）的。）这与 C++ 解析 overloaded functions（重载函数）调用的规则是一致的：在看到一个函数的是否可访问之前，C++ 首先确定与调用匹配最好的那个函数。只有在确定了 best-match function（最佳匹配函数）之后，才检查可访问性。这目前的情况下，两个 checkOuts 具有相同的匹配程度，所以就不存在最佳匹配。因此永远也不会检查到 ElectronicGadget::checkOut 的可访问性。 　　为了消除歧义性，你必须指定哪一个 base class（基类）的函数被调用： mp.BorrowableItem::checkOut(); // ah, that checkOut... 　　当然，你也可以尝试显式调用 ElectronicGadget::checkOut，但这样做会有一个 "you're trying to call a private member function"（你试图调用一个私有成员函数）错误代替歧义性错误。 　 　multiple inheritance（多继承）仅仅意味着从多于一个的 base class（基类）继承，但是在还有 higher-level base classes（更高层次基类）的 hierarchies（继承体系）中出现 MI 也并不罕见。这会导致有时被称为 "deadly MI diamond"（致命的多继承菱形）的后果。 class File { ... };class InputFile: public File { ... };class OutputFile: public File { ... };class IOFile: public InputFile,public OutputFile{ ... }; 　 　在一个“在一个 base class（基类）和一个 derived class（派生类）之间有多于一条路径的 inheritance hierarchy（继承体系）”（就像上面在 File 和 IOFile 之间，有通过 InputFile 和 OutputFile 的两条路径）的任何时候，你都必须面对是否需要为每一条路径复制 base class（基类）中的 data members（数据成员）的问题。例如，假设 File class 有一个 data members（数据成员）fileName。IOFile 中应该有这个 field（字段）的多少个拷贝呢？一方面，它从它的每一个 base classes（基类）继承一个拷贝，这就暗示 IOFile 应该有两个 fileName data members（数据成员）。另一方面，简单的逻辑告诉我们一个 IOFile object（对象）应该仅有一个 file name（文件名），所以通过它的两个 base classes（基类）继承来的 fileName field（字段）不应该被复制。 　　C++ 在这个争议上没有自己的立场。它恰当地支持两种选项，虽然它的缺省方式是执行复制。如果那不是你想要的，你必须让这个 class（类）带有一个 virtual base class（虚拟基类）的数据（也就是 File）。为了做到这一点，你要让从它直接继承的所有的 classes（类）使用 virtual inheritance（虚拟继承）： class File { ... };class InputFile: virtual public File { ... };class OutputFile: virtual public File { ... };class IOFile: public InputFile,public OutputFile{ ... }; 　 　标准 C++ 库包含一个和此类似的 MI hierarchy（继承体系），只是那个 classes（类）是 class templates（类模板），名字是 basic_ios，basic_istream，basic_ostream 和 basic_iostream，而不是 File，InputFile，OutputFile 和 IOFile。 　　从正确行为的观点 看，public inheritance（公有继承）应该总是 virtual（虚拟）的。如果这是唯一的观点，规则就变得简单了：你使用 public inheritance（公有继承）的任何时候，都使用 virtual public inheritance（虚拟公有继承）。唉，正确性不是唯一的视角。避免 inherited fields（继承来的字段）复制需要在编译器的一部分做一些 behind-the-scenes legerdemain（幕后的戏法），而结果是从使用 virtual inheritance（虚拟继承）的 classes（类）创建的 objects（对象）通常比不使用 virtual inheritance（虚拟继承）的要大。访问 virtual base classes（虚拟基类）中的 data members（数据成员）也比那些 non-virtual base classes（非虚拟基类）中的要慢。编译器与编译器之间有一些细节不同，但基本的要点很清楚：virtual inheritance costs（虚拟继承要付出成本）。 　　它也有一些其它方面的成本。支配 initialization of virtual base classes（虚拟基类初始化）的规则比 non-virtual bases（非虚拟基类）的更加复杂而且更不直观。初始化一个 virtual base（虚拟基）的职责由 hierarchy（继承体系）中 most derived class（层次最低的派生类）承担。这个规则中包括的含义： 　　（1） 从需要 initialization（初始化）的 virtual bases（虚拟基）派生的 classes（类）必须知道它们的 virtual bases（虚拟基），无论它距离那个 bases（基）有多远； 　　（2） 当一个新的 derived class（派生类）被加入继承体系时，它必须为它的 virtual bases（虚拟基）（包括直接的和间接的）承担 initialization responsibilities（初始化职责）。 　 　我对于 virtual base classes（虚拟基类）（也就是 virtual inheritance（虚拟继承））的建议很简单。首先，除非必需，否则不要使用 virtual bases（虚拟基）。缺省情况下，使用 non-virtual inheritance（非虚拟继承）。第二，如果你必须使用 virtual base classes（虚拟基类），试着避免在其中放置数据。这样你就不必在意它的 initialization（初始化）（以及它的 turns out（清空），assignment（赋值））规则中的一些怪癖。值得一提的是 Java 和 .NET 中的 Interfaces（接口）不允许包含任何数据，它们在很多方面可以和 C++ 中的 virtual base classes（虚拟基类）相比照。 　　现在我们使用下面的 C++ Interface class（接口类）（参见《C++箴言：最小化文件之间的编译依赖》）来为 persons（人）建模： class IPerson {public:　virtual ~IPerson(); 　virtual std::string name() const = 0;　virtual std::string birthDate() const = 0;}; 　 　IPerson 的客户只能使用 IPerson 的 pointers（指针）和 references（引用）进行编程，因为 abstract classes（抽象类）不能被实例化。为了创建能被当作 IPerson objects（对象）使用的 objects（对象），IPerson 的客户使用 factory functions（工厂函数）（再次参见 Item 31）instantiate（实例化）从 IPerson 派生的 concrete classes（具体类）： // factory function to create a Person object from a unique database ID;// see Item 18 for why the return type isn't a raw pointerstd::tr1::shared_ptr makePerson(DatabaseID personIdentifier); // function to get a database ID from the userDatabaseID askUserForDatabaseID(); DatabaseID id(askUserForDatabaseID());std::tr1::shared_ptr pp(makePerson(id)); // create an object// supporting the// IPerson interface ... // manipulate *pp via// IPerson's member// functions 　　但是 makePerson 怎样创建它返回的 pointers（指针）所指向的 objects（对象）呢？显然，必须有一些 makePerson 可以实例化的从 IPerson 派生的 concrete class（具体类）。 　 　假设这个 class（类）叫做 CPerson。作为一个 concrete class（具体类），CPerson 必须提供它从 IPerson 继承来的 pure virtual functions（纯虚拟函数）的 implementations（实现）。它可以从头开始写，但利用包含大多数或全部必需品的现有组件更好一些。例如，假设一个老式的 database-specific class（老式的数据库专用类）PersonInfo 提供了 CPerson 所需要的基本要素： class PersonInfo {public:　explicit PersonInfo(DatabaseID pid);　virtual ~PersonInfo(); 　virtual const char * theName() const;　virtual const char * theBirthDate() const;　... private:　virtual const char * valueDelimOpen() const; // see　virtual const char * valueDelimClose() const; // below　...}; 　 　你可以看出这是一个老式的 class（类），因为 member functions（成员函数）返回 const char*s 而不是 string objects（对象）。尽管如此，如果鞋子合适，为什么不穿呢？这个 class（类）的 member functions（成员函数）的名字暗示结果很可能会非常合适。 　　你突然发现 PersonInfo 是设计用来帮助以不同的格式打印 database fields（数据库字段）的，每一个字段的值的开始和结尾通过指定的字符串定界。缺省情况下，字段值开始和结尾定界符是方括号，所以字段值 "Ring-tailed Lemur" 很可能被安排成这种格式： [Ring-tailed Lemur] 　　根据方括号并非满足 PersonInfo 的全体客户的期望的事实，virtual functions（虚拟函数）valueDelimOpen 和 valueDelimClose 允许 derived classes（派生类）指定它们自己的开始和结尾定界字符串。PersonInfo 的 member functions（成员函数）的 implementations（实现）调用这些 virtual functions（虚拟函数）在它们返回的值上加上适当的定界符。作为一个例子使用 PersonInfo::theName，代码如下： const char * PersonInfo::valueDelimOpen() const{　return "["; // default opening delimiter} const char * PersonInfo::valueDelimClose() const{　return "]"; // default closing delimiter} const char * PersonInfo::theName() const{　// reserve buffer for return value; because this is　// static, it's automatically initialized to all zeros　static char value[Max_Formatted_Field_Value_Length]; 　// write opening delimiter　std::strcpy(value, valueDelimOpen()); 　append to the string in value this object's name field (being careful to avoid buffer overruns!) 　// write closing delimiter　std::strcat(value, valueDelimClose()); 　return value;} 　 　有人可能会质疑 PersonInfo::theName 的陈旧的设计（特别是一个 fixed-size static buffer（固定大小静态缓冲区）的使用，这样的东西发生 overrun（越界）和 threading（线程）问题是比较普遍的——参见《C++箴言：必须返回对象时别返回引用》），但是请把这样的问题放到一边而注意这里：theName 调用 valueDelimOpen 生成它要返回的 string（字符串）的开始定界符，然后它生成名字值本身，然后它调用 valueDelimClose。 　　因为 valueDelimOpen 和 valueDelimClose 是 virtual functions（虚拟函数），theName 返回的结果不仅依赖于 PersonInfo，也依赖于从 PersonInfo 派生的 classes（类）。 　 　对于 CPerson 的实现者，这是好消息，因为当细读 IPerson documentation（文档）中的 fine print（晦涩的条文）时，你发现 name 和 birthDate 需要返回未经修饰的值，也就是，不允许有定界符。换句话说，如果一个人的名字叫 Homer，对那个人的 name 函数的一次调用应该返回 "Homer"，而不是 "[Homer]"。 　　CPerson 和 PersonInfo 之间的关系是 PersonInfo 碰巧有一些函数使得 CPerson 更容易实现。这就是全部。因而它们的关系就是 is-implemented-in-terms-of，而我们知道有两种方法可以表现这一点：经由 composition（复合）（参见《C++箴言：通过composition模拟“has-a”》）和经由 private inheritance（私有继承）（参见《C++箴言：谨慎使用私有继承》）。《C++箴言：谨慎使用私有继承》 指出 composition（复合）是通常的首选方法，但如果 virtual functions（虚拟函数）要被重定义，inheritance（继承）就是必不可少的。在当前情况下，CPerson 需要重定义 valueDelimOpen 和 valueDelimClose，所以简单的 composition（复合）做不到。最直截了当的解决方案是让 CPerson 从 PersonInfo privately inherit（私有继承），虽然 《C++箴言：谨慎使用私有继承》 说过只要多做一点工作，则 CPerson 也能用 composition（复合）和 inheritance（继承）的组合有效地重定义 PersonInfo 的 virtuals（虚拟函数）。这里，我们用 private inheritance（私有继承）。 　　但 是 CPerson 还必须实现 IPerson interface（接口），而这被称为 public inheritance（公有继承）。这就引出一个 multiple inheritance（多继承）的合理应用：组合 public inheritance of an interface（一个接口的公有继承）和 private inheritance of an implementation（一个实现的私有继承）： class IPerson { // this class specifies thepublic: // interface to be implemented　virtual ~IPerson(); 　virtual std::string name() const = 0;　virtual std::string birthDate() const = 0;}; class DatabaseID { ... }; // used below; details are// unimportant class PersonInfo { // this class has functionspublic: // useful in implementing　explicit PersonInfo(DatabaseID pid); // the IPerson interface　virtual ~PersonInfo(); 　virtual const char * theName() const;　virtual const char * theBirthDate() const; 　virtual const char * valueDelimOpen() const;　virtual const char * valueDelimClose() const;　...}; class CPerson: public IPerson, private PersonInfo { // note use of MIpublic:　explicit CPerson( DatabaseID pid): PersonInfo(pid) {}　virtual std::string name() const // implementations　{ return PersonInfo::theName(); } // of the required　// IPerson member　virtual std::string birthDate() const // functions　{ return PersonInfo::theBirthDate(); }private: // redefinitions of　const char * valueDelimOpen() const { return ""; } // inherited virtual　const char * valueDelimClose() const { return ""; } // delimiter}; // functions 　　在 UML 中，这个设计看起来像这样： 　　这个例子证明 MI 既是有用的，也是可理解的。 　 　时至今日，multiple inheritance（多继承）不过是 object-oriented toolbox（面向对象工具箱）里的又一种工具而已，典型情况下，它的使用和理解更加复杂，所以如果你得到一个或多或少等同于一个 MI 设计的 SI 设计，则 SI 设计总是更加可取。如果你能拿出来的仅有的设计包含 MI，你应该更加用心地考虑一下——总会有一些方法使得 SI 也能做到。但同时，MI 有时是最清晰的，最易于维护的，最合理的完成工作的方法。在这种情况下，毫不畏惧地使用它。只是要确保谨慎地使用它。 　　Things to Remember 　　·multiple inheritance（多继承）比 single inheritance（单继承）更复杂。它能导致新的歧义问题和对 virtual inheritance（虚拟继承）的需要。 　 　·virtual inheritance（虚拟继承）增加了 size（大小）和 speed（速度）成本，以及 initialization（初始化）和 assignment（赋值）的复杂度。当 virtual base classes（虚拟基类）没有数据时它是最适用的。 　　·multiple inheritance（多继承）有合理的用途。一种方案涉及组合从一个 Interface class（接口类）的 public inheritance（公有继承）和从一个有助于实现的 class（类）的 private inheritance（私有继承）。 关于虚拟继承的思考虚拟继承在一般的应用中很少用到，所以也往往被忽视，这也主要是因为在C++中，多重继承是不推荐的，而一旦离开了多重继承，虚拟继承就完全失去了存在的必要（因为这样只会降低效率和占用更多的空间，实在是一无是处）。　　以下面的一个例子为例：　　#include 　　#include 　　class CA　　{　　 int k; //为了便于说明后面的内存结构特别添加　　public:　　 void f() {cout << "CA::f" << endl;}　　};　　class CB : public CA　　{　　};　　class CC : public CA　　{　　};　　class CD : public CB, public CC　　{　　};　　void main()　　{　　 CD d;　　 d.f();　　}　　当编译上述代码时，我们会收到如下的错误提示：　　error C2385: 'CD::f' is ambiguous　　即编译器无法确定你在d.f()中要调用的函数f到底是哪一个。这里可能会让人觉得有些奇怪，命名只定义了一个CA::f，既然大家都派生自CA，那自然就是调用的CA::f，为什么还无法确定呢？　　这是因为编译器在进行编译的时候，需要确定子类的函数定义，如CA::f是确定的，那么在编译CB、CC时还需要在编译器的语法树中生成CB::f，CC::f等标识，那么，在编译CD的时候，由于CB、CC都有一个函数f，此时，编译器将试图生成两个CD::f标识，显然这时就要报错了。（当我们不使用CD::f的时候，以上标识都不会生成，所以，如果去掉d.f()一句，程序将顺利通过编译）　　要解决这个问题，有两个方法：　　1、重载函数f()：此时由于我们明确定义了CD::f，编译器检查到CD::f()调用时就无需再像上面一样去逐级生成CD::f标识了；　　此时CD的元素结构如下：　　--------　　|CB(CA)|　　|CC(CA)|　　--------　　故此时的sizeof(CD) = 8;（CB、CC各有一个元素k）　　2、使用虚拟继承：虚拟继承又称作共享继承，这种共享其实也是编译期间实现的，当使用虚拟继承时，上面的程序将变成下面的形式：　　#include 　　#include 　　class CA　　{　　 int k;　　public:　　 void f() {cout << "CA::f" << endl;}　　};　　class CB : virtual public CA　　{　　};　　class CC : virtual public CA　　{　　};　　class CD : public CB, public CC　　{　　};　　void main()　　{　　 CD d;　　 d.f();　　}　　此时，当编译器确定d.f()调用的具体含义时，将生成如下的CD结构：　　----　　|CB|　　|CC|　　|CA|　　----　　同时，在CB、CC中都分别包含了一个指向CA的vbptr（virtual base table pointer），其中记录的是从CB、CC的元素到CA的元素之间的偏移量。此时，不会生成各子类的函数f标识，除非子类重载了该函数，从而达到“共享”的目的。　　也正因此，此时的sizeof(CD) = 12（两个vbptr + sizoef(int)）;