都是O(1)时间复杂度，Bitmap、Array、HashMap有什么区别？

本文发表于入职啦(公众号: ruzhila) 大家可以访问入职啦学习更多的编程实战。

查找效率最高的算法的时间复杂度为O(1)的数据结构有：数组、位图、哈希表三种，我们了解一下三种数据结构的特点和使用区别。

数组

所有的开发语言都提供了数组这种数据结构，数组是一种线性表数据结构，它是由相同类型的元素按照一定的顺序排列而成的集合。数组的特点是：支持随机访问，时间复杂度为O(1)。

数组的优点：

支持随机访问，时间复杂度为O(1)。
数组在内存中是连续存储的，所以可以利用CPU的缓存机制，访问效率高。
数组的实现简单，易于理解，无需依赖其他数据结构，并且内存占用是固定的，也是就是如果数组的长度是n，那么数组占用的内存空间就是n * 元素的大小。

数组的缺点：

数组的长度是固定的，如果数组的长度不够，需要重新分配内存，然后将原数组的数据拷贝到新数组中，不同的语言对于数组的扩容策略不同，但是都会有一定的性能损耗。你可以理解大部分的扩容都是O(n)的时间复杂度。
数组的删除和插入操作的时间复杂度为O(n)，因为需要将插入位置后面的元素都向后移动一位。
数组的元素类型必须相同，虽然有些高级语言比如Java、Go、Python等支持Object类型，但是这样会导致类型转换的性能损耗。

数组的应用场景：

数组适合存储元素类型相同的数据
需要随机访问的场景
不需要频繁的插入和删除操作

HashMap

除了C语言，大部分语言都提供了HashMap的实现，HashMap是一种键值对存储的数据结构，属于应用最广泛的数据结构之一。HashMap的特点是：支持O(1)时间复杂度的查找、插入、删除操作。虽然HashMap的时间复杂度是O(1)，但是在极端情况下，HashMap的时间复杂度可能会退化为O(n)，这是因为HashMap的实现是基于哈希表的，哈希表的性能取决于哈希函数的设计和哈希冲突的处理。

如果哈希函数无法生成均匀分布的哈希值，或者哈希冲突的处理不当，那么HashMap的性能可能会大打折扣。当不同的Key的哈希值相同，那么就会发生哈希冲突，这时候HashMap就需要通过链表、红黑树等数据结构来解决哈希冲突。

你可以理解HashMap的数据实际的存储结构是一个数组，数组的每个元素是一个链表或者红黑树，链表或者红黑树的每个节点是一个键值对。

class Entry {
    K key;
    V value;
}

class HashMap {
    private List<Entry>[] table;

    public void put(K key, V value) {
        int index = hash(key);
        List<Entry> list = table[index%table.length];
        for (Entry entry : list) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }
        list.add(new Entry(key, value));
    }
}

HashMap的优点：

支持O(1)时间复杂度的查找、插入、删除操作。
支持丰富的类型，键和值的类型可以不同。
插入和删除操作的时间复杂度为O(1)。

HashMap的缺点：

每次操作Key的时候都需要计算哈希值，这个会产生一定的性能损耗。
HashMap的内存占用比较大，因为HashMap的实现是基于哈希表的，少量的Key也会预先分配一个连续的内存空间。典型的用空间换时间的策略。

Bitmap

Bitmap是一个非常少用的数据结构，它的特点是：支持O(1)时间复杂度的查找、插入、删除操作，但是Bitmap的应用场景非常有限，只适合存储0和1的数据。如果有100玩的用户，要计算用户是否已经注册，如果使用数组，那么需要100万个Boolean类型的元素，如果使用HashMap，那么需要100万个键值对，这样会占用大量的内存空间。

我们的需求只是想知道用户是否已经注册，只需要知晓状态0和1，那么最小的存储单位就是Bit，如果用boolean，那么至少是8bit，也就是1个字节，如果使用Bitmap，那么只需要1bit，也就是1/8个字节。

所以当需要存储100w的用户是否注册的状态时，使用Bitmap只需要1M内存，换成数组就是100w个字节～=8M内存。内存占用就减少了8倍。

当需要计算一个index的下表是否存在时，只需要将找到的index对应的bit位设置为1，如果需要删除，那么将对应的bit位设置为0。

class Bitmap {
    private byte[] data;

    public void set(int index, boolean value) {
        int byteIndex = index / 8;
        int bitIndex = index % 8;
        if (value) {
            data[byteIndex] |= (1 << bitIndex);
        } else {
            data[byteIndex] &= ~(1 << bitIndex);
        }
    }

    public boolean get(int index) {
        int byteIndex = index / 8;
        int bitIndex = index % 8;
        return (data[byteIndex] & (1 << bitIndex)) != 0;
    }
}

总结

总结一下三种数据结构的特点和应用场景：

数据结构	插入	删除	查找	内存占用	应用场景
数组	O(n)	O(n)	O(1)	n * 元素大小	元素类型相同，需要随机访问的场景
HashMap	O(1)	O(1)	O(1)	大	键值对存储，需要O(1)时间复杂度的查找、插入、删除操作
Bitmap	O(1)	O(1)	O(1)	小	只需要存储0和1的数据，内存占用小，适合大数据量的场景

这是三种都是O(1)时间复杂度的数据结构，但是应用场景不同，需要根据场景选择合适的数据结构。

作为后端开发工程师，我们需要了解数据结构的基本原理和应用场景，这样才能更好地优化代码，提高系统的性能。

所有的后端面试常见的问题，我们每天都会在我们的编程群里面讨论和Code review, 欢迎大家加入我们的编程群，一起学习和进步。

编程交流群

欢迎大家关注入职啦 (公众号: ruzhila) ，获取更多有趣的编程挑战题和技术干货！