分类：Java

算法思路

对一组数据排序,如果我们能事先知道数组的范围比如我们的”待排序数组A[]”所有的数字都在0到10之间,那我们可以初始化一个数组B[]大小就是10,默认值都是0(这里为了方便叙述,所有数组下标从1开始),A数组从头到尾遍历,比如第一个数字是5,那B[5]=1,第二个数是3那B[3]=1,第三个数字是5那B[5] = B[5]+1=2,以此类推获得数组B,此时B数组里面index即原数组A里面的数字,value为A数组里面值为index的数字出现了几次,遍历所以遍历B数组打印每打印一次A[index]-1直到A[index]=0,这样我们就将所有的数字排序打出

举例

问题

① 数组大小可以为max-min+1减小空间复杂度比如[99,100]其实size为2就够了

② 如何让排序稳定,比如{6,5,5}我们给5编一个号码方便简述5a,5b,如果是上边的方式5a和5b其实是不稳定的,但是如果我们可以对原数组进行累加,原有多少个index数组,就变成有多少个数字比index小了,例如上边的数组,辅助数组为{2,1}->{2,3}然后将{6,5a,5b}从后到前遍历,5b放到index为2的地方{2,3}->{1,3},然后遍历到5a,5a放到index为1的地方,最后6放到index为3的地方得到{6,5a,5b}稳定排序

put

• 判断是否有tab[],没有证明还没有初始化,先初始化(容量,threadHold)
• 对key hash后和length-1与寻找bucket,如果bucket为空放入,如果不为空但是key相同换掉,如果是treeNode证明已经树化,调用putTreeVal,否则是链化的,向下寻找找到key相同的或者链的tail插入(尾插),并判断是链的容量是否到了树化的临界点,到了把tab树化最后判断是否需要扩容,最后把oldVal返回
• 问题: 如何树化,树化之后的putTreeVal如何操作,如何扩容

get

• 1.获得key的hash,和length-1求与得到bucket的firstNode,如果key相同返回value不同判断是不是treeNode,是的话调用getTreeNode,不是的话顺着链向下找直到key相同返回相应的value或者是null
• 问题: treeNode如何get

如何树化

• 当链表超过8个,就会树化,如果链表的size比较小,还会扩容(为什么扩容) 第一次树化只是由node变成treenode,维护了pre和next指针,但是并没有真正树化真的树化,应该是第一次putTreeVal的时候树化之后入会putTreeVal找到树的root,通过hash值寻找root大的dir+,小的dir-如果key相同返回p,如果key不同,但是hash相同,看下key有没有实现compator类如果没有实现或者实现了,但是compator之后也相同,就search当前的节点直到找到应该插入的地方,如果找不到(key不同compator相同)只能调用system的hash方法然后调整树至平衡

treeNode如何get

• 找到root,根据hash值find

扩容

remove

• 根据key获得bucket的index,然后寻找需要被remove的node同理寻找的过程也分为链化和树化的节点
• 链化的:不断next判断key是否相同,找到之后直接通过指针把找到的noderemove了
• 树化的:和get中寻找treeNode相同,先找到目标节点

注: remove有的会去匹配value的值,如果key的value和传入的value不同
不可以删除当前节点