c chaîne de comparer vs hachage comparer

Est la comparaison va être fait une fois ou plusieurs fois? Si la comparaison va être fait en une seule fois, alors vous êtes probablement mieux de faire une comparaison directe. Si vous allez avoir besoin de comparer les très nombreuses chaînes à cet ensemble de chaînes constantes, alors vous pouvez probablement économiser du temps dans le long terme, en le faisant avec les tables de hachage.

C'est un simple problème assez que vous pouvez facilement écrire des deux manières et voir ce qui fonctionne le mieux pour un ensemble représentatif de l'entrée.

OriginalL'auteur Tyler McHenry

Il est difficile de prendre de l'avance, la chaîne de fonctions de hachage sont des O(n). Comparaison de chaînes de caractères est O(n) ainsi, avec une petite Oh. Vous ne serait d'avance si vous pouvez stocker les valeurs de hachage permet de calculer et de les utiliser à plusieurs reprises. Pour tous les deux.

Simple échantillon C fonctions de hachage sont ici.

OriginalL'auteur Hans Passant

Je pense que si vous avez une liste statique de chaînes, je voudrais stocker dans un tableau trié, puis utiliser bsearch pour déterminer si une chaîne est dans la liste. Cette méthode retourne NULL si il n'existe pas, ou un pointeur vers la valeur doit exister, et est probablement plus rapide qu'un linéaire de recherche ou de hachage.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* cmp function for qsort and bsearch */
static int pstrcmp(const void *a, const void *b)
{
  return strcmp(*(char * const *)a, *(char * const *)b);
}

/* check an input against the list of known strings */
static char *check_for_match(char *input)
{
  static char *static_list[] = { "one", "two", "three", "four", "five" };
  static int nelems;

  /* this sorts the list, for demonstration purposes, but if the list
     is static then it could be sorted prior to compiling */
  if (! nelems)
  {
    nelems = sizeof(static_list) / sizeof(*static_list);
    qsort(static_list, nelems, sizeof(*static_list), pstrcmp);
  }


  return bsearch(&input, static_list, nelems, sizeof(*static_list), pstrcmp);
}

int main(int argc, char *argv[])
{
  if (check_for_match("should_not_match"))
  {
    printf("Match found.\n");
  } else {
    printf("No match found.\n");
  }

  if (check_for_match("two"))
  {
    printf("Match found.\n");
  } else {
    printf("No match found.\n");
  }
  return EXIT_SUCCESS;
}

OriginalL'auteur Brandon Horsley

Si vos chaînes constantes sont connus au moment de la compilation, prendre un coup d'oeil à l'idée d'un "idéal de hachage".

Wikipedia: Une fonction de hachage parfait pour un ensemble S est une fonction de hachage qui mappe des éléments distincts dans S distincts entiers, sans collision.

Que "sans collision" chose vous permet d'économiser du travail. Des possibilités de lecture et les mises en œuvre sont:

• cmph -- http://cmph.sourceforge.net/
• gperf -- http://www.gnu.org/software/gperf/

OriginalL'auteur Darron

Une autre approche qui permettrait de travail, est à votre chaîne constante triés et faire une recherche dichotomique de votre chaîne, de cette façon, vous n'avez à la plupart des log2(n) comparaisons (par exemple, seulement 10 des comparaisons pour du 1024 chaînes ou même seulement 20 pour 1000000 de chaînes de caractères).
Je ne sais pas si c'est applicable à votre problème, mais j'ai eu de très bons résultats avec cette approche. Le hachage est vraiment difficile d'obtenir le droit, le coin des cas, peuvent devenir vraiment vicieux et le calcul de la clé peut souvent être très coûteux.

OriginalL'auteur Patrick Schlüter