hashMap一些知识点的冲突

Question

老师好：

1. 面试的时候，面试官说bucket是指table这一段，而不是图中链表这一段。。不知道哪个对了

2. 扩容的时候，老师是说容量为什么是2^n次方，是说内部有个高效取模算法是需要入参是2^n，但是面试官说是因为除了第一次取模后，后序扩容都是2倍，用再hash运算，扩容的时候是比如{1,2,3,4}扩容就变成{1,3}+{2,4}这样错位移动到扩容的位置。。这个说法是对的么

3. 问了红黑树的红和黑代表什么。。红黑树找了文章看不懂。有没有比较简单的描述
   

Answer 1

翔仔 2020-06-25 03:59:21

同学好，

1. 当hashmap建立时会创建一个数组，这个数组中存储元素的位置是一个桶bucket；

2. 是对的呀，因为高效取模算法的意义，扩容的意义在于减少冲突，也就是将数据均匀散落在各个bucket中

3. 推荐一个链接 https://www.sohu.com/a/202490920_468650

• 提问者 莨菽菽 #1

  1.老师你的意思是element这个数组位置是一个bucket，而不是说链表是一个Bucket是吧？
  2.面试官说扩容的时候因为都是二倍，移动的时候也是移动比如{1,2,3,4}扩容就变成{1,3}+{2,4}这样错位移动，所以不需要rehash，是不需要rehash了么？

• 翔仔 回复 提问者 莨菽菽 #2

  1.是的哈，数组元素就是bucket
  2.移动的时候就是rehash的过程呀，扩容后会把数据重新移动也就是rehash

• 提问者 莨菽菽 #3

  非常感谢！