在探讨这个问题之前，最好先看下Java集合之HashMap存储这篇文章
HashMap的存储结构是数组+链表或者数组+红黑树
查找一个key所对应的的value值时
1：先对key做hash算法，找到数组中的索引 ；复杂度为1；o(1).可以想想为啥数组的复杂度为1？
2：再遍历改索引对应的数组元素中的链表或者红黑树，如果是链表，平局查找复杂度为n/2;如果是红黑树，平均查找复杂度是log(n)
所以综合以上两步很容易算出复杂度
我们再想想为什么？
为什么数组的复杂度为1？
这个很容易，因为所有的数组在内存中都是连续的，数组的内存地址其实也就是数组中首位元素的地址，数组中每个单元相互间的偏移地址是固定的，如一个int[] ,在Java中每个元素便宜4个字节，首个元素地址已知，偏移地址已知，查找第n个元素的地址=数组地址+n*偏移地址；一次就可以算出，直接查找出，所以数组按索引查找效率非常高
为什么链表的平均复杂度为n/2？
也容易理解，遍历n个元素，逐个对比，每个位置都有可能出现，折中就是n/2
为什么红黑树的平均复杂度为n/2？
笔者也是到网上参考。读者可以自行搜索。
网友评论