• 数组和哈希表
    • Collection
    • List
    • ArrayList
    • Map
    • HashMap

    1，数组和哈希表的区别
    数组也是映射，哈希表也是映射，而且都是一对一的映射，那么使用数组和使用哈希表有什么区别呢？

    ——内存分配问题

    数组的下标是从0到n-1，如果我们需要使用一个下标为1000的映射，那么我们就要创建一个内存容量为1000的数组。

    哈希表的作用主要是为了解决稀疏数组对空间大量浪费的问题。

    如果我们只需要用1,3,100这三个下标，如果用数组，我们需要创建一个内存容量为100的数组，这非常浪费空间，我们只使用了3%的内存，而且当我们需要新增下标为1000的数据的时候，我们的内存将会变得非常巨大。

    不过，在实际的工程中，一个好的散列函数会尽可能的让其存储均匀分布，不褪变成稀疏数组而是保持成为普通数组，如此一来，可以通过选择良好的散列函数避免存储稀疏数组的开销，这也算是散列函数选择的技巧了。
    哈希表可以理解为一维数组。因为只是单一的坐标。当然如果考虑到哈希碰撞，理解为二维数组也无不可。
    至于下标1跟10001，这个问题很好。你观察到了，这样的数组会有大量的空洞。这是一种常见的现象。
    一维的这种数组叫做稀疏数组，二维的这种数组叫做稀疏矩阵。而对稀疏数组跟稀疏矩阵都有专门的保存算法。
    从数学角度，哈希表可能是个稀疏数组，或者如果你认为它是二维的话，那就是个稀疏矩阵，如果这样的话，在存取时，它往往需要用专门的办法优化其存储占用。