¿Qué estructura de datos es apropiado para esta situación?

Question

Estoy tratando de decidir qué estructura de datos que se utilizará para almacenar pares clave-valor, cuando sólo son características necesarias

• inserción
• Buscar

En concreto, no necesito ser capaz de eliminar pares, o se puede recorrer llaves / valores / pares.

Las teclas son tuplas de números enteros, los valores son punteros (referencias, lo que sea). Sólo estoy almacenar un par de millones de pares repartidos a lo largo de (muchos) los objetos.

Actualmente estoy considerando utilizando

• una tabla hash
• una kd-árbol
• un árbol B

Me estoy inclinando hacia la tabla hash (para la inserción de tiempo O(1) / lookup), pero quería confirmar mis inclinaciones.

¿Qué estructura (de los de arriba o de otro tipo) me recomienda y por qué? Si desea recomendar una tabla hash, debería crear una tabla separada para cada objeto, o simplemente crear una sola tabla y utilizar el id del objeto como parte de la tupla clave?

Answer 1

Una tabla hash será la mejor opción aquí como todas las operaciones que le interesan son O (1) (y, como tal, debería no tiene que preocuparse acerca de cómo crear múltiples tablas hash).

Answer 2

Soy un gran fan de las tablas hash, ya que son fáciles y hay implementaciones disponibles para casi todos los idiomas principales que hay. La O (1) de inserción / búsqueda es una especialmente buena característica.

Probablemente debería utilizar una sola tabla, para guardar en la memoria. Las tablas hash son la memoria en cuanto notoriamente ineficiente, y el uso de una sola tabla ayudarían a minimizar ese.

Answer 3

Las tablas hash serían útiles aquí y no veo ninguna razón para tener más de una tabla.

Answer 4

La mayoría de los árboles tienen un O (n ln n) de tiempo de búsqueda, pero tablas hash tienen un O (1) tiempo de búsqueda, por lo que esa es la que desea utilizar. También es muy común, ya menudo la aplicación está altamente optimizado para arrancar.