Tabela hash tratamendo de colisão dados em arquivos

Programação
#1

Olá pessoal, como faço para tratar as colisões de uma tabela hash onde os dados então em um arquivo. Possuo um classe tabela hash que tem uma lista de lista encadeada e a função de disperção (método da divisão) entre outros e uma classe hash que tem como atributos chave e valor. Até o momento estou fazendo tudo em memória principal e está funcionando , só que agora preciso fazer com que o atributo valor do par chave e valor da hash seja um ponteiro para o arquivo onde estarão as informações correspondentes a chave procurada, ou seja, o atributo valor da hash me indicara quantos bytes preciso deslocar no arquivo para encontrar as informações correspondentes a chave. O problema é o que devo fazer quando houver colisão? Na memória principal quando há colisão, apenas se inseri o elemento na próximo nó vago da lista encadeada(encadeamento externo), como possor tratar isso mexendo em arquivo?

#2

eu não sei como vc esta usando arquivo, mas existem diversas tecnicas:

imagine um arquivo assim:

<arquivo hash="3748237432">
  <no>
     <chave>pato</chave>
     <valor>batata</valor>
  </no>
  <no>
    <chave>misterio</chave>
    <valor>lombriga</valor>
  </no>
  <no>
    <chave>teste</chave>
    <valor>666</valor>
   </no>
</arquivo>

perceba que basta parsear este arquivo que usando qq api xml vc percorre todos os nos ate achar a chave certa.

vc nao precisa usar xml, pode usar um layout ultra simples em bytes

blob = chave + byte separador + valor
sessao = tamanho do blog em bytes + blob
arquivo = sessao1 + sessao2 + sessao3

do nosso exemplo, imagine o byte 0x00 como separador:

blob1 = p, a, t, o, 0x00, b, a, t, a, t, a
sessao1= 11, p, a, t, 0, 0x00, b, a, t, a, t, a

blob2 = m, i, s, t, e, r, i, o, 0x00, l, o,m, b, r,i, g, a
sessao2= 17, m, i, s, t, e, r, i, o, 0x00, l, o,m, b, r,i, g, a

ou seja vc tem um arquivo
11pato\0batata17misterio\0lombriga

e fica relativamente simples de encontrar basta que vc controle os bytes que le.

para adicionar basta add ao fim.

se vc quer mais segurança vc pode criar um arquivo mais complexo, com mais bytes de controle, etc. algo como : começo e fim de sessao, etc. só garanta que os bytes que vc vai usar nao estarao presentes no byte do conteudo ou chave ou da zika.

vc tb pode fazer

blob = tamanho da chave + chave + tamanho do conteudo + conteudo

sua vez :slight_smile:

Tabela Hash em arquivo