Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package closehashes;
- public class Dict {
- private int CAPACITY = 10; // количество классов в словаре
- private char[][] a; // массив символьных массивов имён
- private static boolean arraysEqual(char[] a, char[] b) { // Метод проверки массивов на равенство
- if (a == b) return true;
- for (int i = 0; i < a.length; i++) {
- if (a[i] != b[i]) return false;
- if (a[i] == 0) break;
- }
- return true;
- }
- private static char[] generateCharArray(String s){
- char[] out = new char[10];
- for (int i=0; i<out.length; i++)
- out[i] = s.charAt(i);
- return out;
- }
- public Dict() { // Конструктор по умолчанию, выделяет память на массив классов
- a = new char[CAPACITY][];
- }
- public Dict(int n) { // Принимает количество возможных элементов множества (область определения)
- CAPACITY = n;
- a = new char[CAPACITY][];
- }
- private int computeHash(char[] a) { // todo метод считает значение хэша
- int out = 0;
- for (int i = 0; a[i] != 0 && i < 10; i++)
- out += a[i];
- return out;
- }
- private int repeatHash(int hash, int i) { // метод считает повторный хэш для существующего хэша i -- номер повторного хэширования
- return (hash + i) % CAPACITY;
- } // todo функция хэширования
- private int find(char[] name){ // метод ищет имя в массиве и возвращает индекс, если его нет, возвращает -1
- // посчитать хэш
- int hash = computeHash(name);
- int i=0; // Номер повторения
- int startInd = repeatHash(hash, i++);
- // проверить на равенство имени если элемент пустой, вернуть -1
- if (a[startInd] == null) return -1;
- // Если нашли совпадение возвращаем индекс найденного имени
- if (arraysEqual(name, a[startInd])) return startInd;
- // создать переменную повторного хэша
- int nextInd=repeatHash(hash, i++);
- // Цикл повторных хэширований пока не вернулись в ту же позицию или не наткнулись на пустой
- while (a[nextInd] != null && nextInd != startInd) {
- if (arraysEqual(name, a[nextInd])) return nextInd; // если нашли, возвращаем позицию
- nextInd = repeatHash(hash, i++); // пересчитываем хэш
- }
- return -1; // если не нашли то элемента нет
- }
- public boolean MEMBER(String x) { // метод проверяет наличие имени в словаре
- char[] name = generateCharArray(x); // Сформировать массив символов
- //найти имя через find
- int ind = find(name);
- return (ind != -1); // Если вернулся не -1, то имя есть в словаре
- }
- public void INSERT(String x) { // метод вставляет имя в словарь, если его ещё там нет
- char[] name = generateCharArray(x); // Сформировать массив символов
- // посчитать хэш
- int hash = computeHash(name);
- int i=0; // Номер повторения
- int startInd = repeatHash(hash, i++);
- // проверить на равенство имени если элемент пустой, вернуть -1
- if (a[startInd] == null) {
- a[startInd] = name;
- return;
- }
- if (arraysEqual(name, a[startInd])) return ;
- // создать переменную повторного хэша
- int nextInd=repeatHash(hash, i++);
- int first_deleted = -1; // Переменная запоминающая индекс первого найденного удалённого
- if (a[startInd][0] == 0) first_deleted = startInd; // если в первом элементе удалённое имя, сразу запоминаем
- while (a[nextInd] != null && nextInd != startInd) { // Цикл повторных хэширований пока не вернулись в тот же хэш или не наткнулись на пустой
- if (arraysEqual(name, a[nextInd])) return; // если нашли выходим
- // если не был найден ещё удалённый и нашли такой запоминаем
- if (first_deleted == -1 && a[nextInd][0] == 0) first_deleted = nextInd;
- nextInd = repeatHash(hash, i++); // пересчитываем хэш
- }
- if (nextInd == startInd) throw new MyException("Словарь заполнен"); // если мы вернулись к тому же хешу, словарь заполнен
- a[(first_deleted == -1)? nextInd: first_deleted] = name; // вставляем имя в удалённый, если он был, иначе туда, куда пришли
- }
- public void DELETE(String x) { // почему бы при проходе для удаления не искать предыдущий а поменять контенты со следующим и удалить следующий
- char[] name = generateCharArray(x); // Сформировать массив символов
- //найти имя через find
- int ind = find(name);
- if (ind == -1) return; // если индекс -1 то такого элемента нет, ничего не делаем
- //записываем в начало символьного массива терминальный символ
- a[ind][0] = 0;
- }
- public void MAKENULL() { // Зануление голов связных списков
- for (int i = 0; i < CAPACITY; i++)
- a[i] = null;
- }
- public void PRINT(){
- for (int i=0; i<CAPACITY; i++){
- if (a[i] != null && a[i][0] != 0) {
- System.out.print(a[i]);
- System.out.print(" ");
- }
- }
- System.out.println();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement