记录一道面试题（哈希表 稀疏矩阵）

题目：

有一个游戏中的三维地图，是由i，j，k三个轴组成的三维网络。每个立方体由不同的种类代表，比如空气，水，沙子，泥土。
地图上方的空气方块，不会经常变动且数量占大多数，下方是各种类型的方块，会经常相互转换（水变沙子，沙子变泥土等）。

问题：请你实现一个存储该地图的方案（地图方块和对应类型）。
要求：尽量减少内存空间占用，要支持高频查询。

思路：

1.首先要有整体意识，地图是一个三维坐标系，有三个轴。应该要想到用矩阵或者多维数组。

2.要注意要求中的“尽量减少内存空间占用”，由于空气多且不易变动，可以采用稀疏矩阵来存。相当于没数据的时候就是空气。

3.要支持高频查询，哈希表应该是最快的。

上代码：

blockmap.h

#ifndef BLOCKMAP_H
#define BLOCKMAP_H#include <unordered_map>/*
有一个游戏中的三维地图，是由ijk三个轴组成的三维网络。每个立方体由不同的种类代表，比如空气，水，沙子，泥土。
地图上方的空气方块，不会经常变动且数量占大多数，下方是各种类型的方块，会经常相互转换（水变沙子，沙子变泥土等）。问题：请你实现一个存储该地图的方案（地图方块和对应类型）。
要求：尽量减少内存空间占用，要支持高频查询。关键思路：
1.由于空气变动少且占用多，可以采用稀疏矩阵存储，节省内存资源。
2.用哈希表存储非空气块，方便快速查询。
*/// 方块类型：实际项目应该还会存储别的成员。比如颜色之类的。也可以用枚举定义类型
struct Block
{int type = 0; // 0-空气 1-水 2-泥土 3-沙子 4-树
};class BlockMap
{
private:std::unordered_map<long long, Block> blockMap; // 用哈希表存储非空气块，方便快速查询。const int airType = 0; // 空气类型为0long long encodeKey(const int& i, const int& j,const int& k) // 为了生成唯一的key，合并成一个long long
    {return (static_cast<long long>(i) << 40) | (static_cast<long long>(j) << 20) | k;}
public:BlockMap(){}//获取方块类型int getBlockType(const int& i, const int& j,const int& k){long long key = encodeKey(i,j,k);if(blockMap.find(key) != blockMap.end()){return blockMap[key].type;}else{return airType; // 找不到的时候，默认就是空气。
        }}// 设置方块类型void setBlockType(const int& i, const int& j,const int& k, const int& type){auto key = encodeKey(i,j,k);if(type == airType){return; // 不存空气。节省内存空间。
        }else{Block newbk;newbk.type = type;blockMap[key] = newbk;}}
};void BlockMapTest(); // 测试程序#endif // BLOCKMAP_H

测试：

#include "blockmap.h"
#include <qDebug> // Qt平台的头文件。非C++标准库void BlockMapTest()
{BlockMap mapTest;mapTest.setBlockType(1,1,1,1);mapTest.setBlockType(2,2,2,2);mapTest.setBlockType(3,3,3,3);qDebug() << "1,1,1 类型为:" << mapTest.getBlockType(1,1,1);qDebug() << "2,2,2 类型为:" << mapTest.getBlockType(2,2,2);qDebug() << "3,3,3 类型为:" << mapTest.getBlockType(3,3,3);qDebug() << "1,0,1 类型为:" << mapTest.getBlockType(1,0,1);
}

执行效果：

总结：

数据结构还是要多熟悉，自己写不出来的话要会选择最合适的。