public class LinearProbingHashST< Key, Value> { private int N; private int M = 16; private Key[] keys; private Value[] vals; public LinearProbingHashST( ) { keys = (Key[]) new Object[M]; vals = (Value[]) new Object[M]; } private int hash( Key key) { return (key.hashCode( ) & 0x7fffffff) % M; } private void resize( int cap) { LinearProbingHashST< Key, Value> t; t = new LinearProbingHashST< Key, Value>( cap); for (int i = 0; i < M; i++) if (keys[i] != null) t.put( keys[i], vals[i]); keys = t.keys; vals = t.vals; M = t.M; } public void put( Key key, Value val) { if (N >= M/2) resize(2*M); int i; for (i = hash( key); keys[i] != null; i = (i+1) % M) if (keys[i].equals( key)) { vals[i] = val; return; } keys[i] = key; vals[i] = val; N++; } public Value get( Key key) { int i; for (i = hash( key); keys[i] != null; i = (i+1) % M) if (keys[i].equals( key)) return vals[i]; return null; } } Código adaptado de |
O tema dessas notas é o mesma de boa parte da Ciência/Engenharia da Computação: a construção de programas rápidos, programas que resolvem problemas de maneira eficiente (ou seja, sem desperdício de tempo).
O segredo de muitos programas rápidos está na maneira como seus dados são organizados durante o processamento, ou seja, na estrutura de dados (data structure) empregada pelo programa. Muitas vezes, a melhor maneira de organizar os dados não é óbvia nem simples. Mas uma boa estrutura de dados tem um efeito dramático sobre a velocidade do programa. (É o caso, por exemplo, da estrutura conhecida como árvore rubro negra.)
O estudo de boas estruturas de dados é o assunto central destas notas. Isso envolve, em particular, o estudo de algoritmos para a criação e manipulação dessas estruturas. Assim, o título deste sítio poderia ser Algoritmos e Estruturas de Dados.
Conteúdo deste sítio:
Pré-requisito: Supõe-se que o leitor já teve um curso de introdução à programação e um curso de projeto de algoritmos.
Quais foram as disciplinas mais importantes
que você cursou no BCC
(Bacharelado em Ciência da Computação na USP)?
Resultado de levantamento feito entre ex-alunos
(2009-2013):
Outros assuntos: Exercícios de Teoria dos Grafos | Graph Theory Exercises | Uma Introdução Sucinta à Teoria dos Grafos | Otimização Combinatória | Minicurso de Análise de Algoritmos | Análise de Algoritmos | O que é uma prova? | Projeto de Algoritmos em C | Digrafos | Algoritmos para Grafos via Sedgewick | Literate Programming & CWEB | Algoritmos de Programação Linear | Uma Introdução Sucinta a Algoritmos de Aproximação