Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# .NET
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.69/74: Рейтинг темы: голосов - 74, средняя оценка - 4.69
ТохаSk8
0 / 0 / 0
Регистрация: 17.10.2009
Сообщений: 25
1

Создать хеш таблицу

17.10.2009, 13:00. Просмотров 13426. Ответов 26
Метки нет (Все метки)

Нужно создать хеш-таблицу вида:Страна=стоймость,Страна=стоймость.Для пользователя предкмотреть выбор нескольких стран для поехдки с указание общей стоимости путешествия.
Приложение консольное, с хеш таблицами вообще не знаком, почитал в книжке ничего не понял...Плиз хелп
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.10.2009, 13:00
Ответы с готовыми решениями:

Как создать хеш для строки и вернуть строку из хеша
Привет! У меня есть словарь из 200 тыс. уникальных слов. Слова состоят...

MD5 хеш. Где истина?
использую метод выложеный на MSDN по нахождению MD5 от строки public...

Как получить MD5-хеш файла
Добрый дннь уважаемые форумчане. Хотел бы у вас поинтересоваться. Собственно...

Проект алгоритма хеш функции SHA256
Доброго всем времени, подскажите, как запустить сие код? Должно выполняться...

Работа с Хеш-таблицами c использованием HashTable
Требуется добавлять, извлекать и удалять элементы из Хеш-таблицы. В С# имеется...

26
Rififi
2363 / 1056 / 104
Регистрация: 03.05.2009
Сообщений: 2,656
17.10.2009, 13:11 2
гооглить Hashtable, IDictionary<>
0
ТохаSk8
0 / 0 / 0
Регистрация: 17.10.2009
Сообщений: 25
17.10.2009, 23:01  [ТС] 3
погуглил ничего не понял=(((
0
Goldywhite
45 / 45 / 3
Регистрация: 18.10.2009
Сообщений: 119
19.10.2009, 00:48 4
C#
1
2
3
4
5
6
7
8
9
Hashtable ht = new Hashtable();
ht["rus"] = 1000;
ht["gb"] = 2000;
ht["fr"] = 3000;
Console.WriteLine("Введите код страны (rus, gb,fr)");
string country = Console.Readline().Trim();
object res = ht[country];//внимание! res - object. Чтобы работать с ним как с числом надо будет сделать приведение (int)res
if(res == null) Console.WriteLine("Введён неправильный код страны");
else Console.WriteLine("поездка в выбранную страну ({0}) стоит {1} рублей", country, res);
0
Kpactu
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 3
22.11.2009, 11:56 5
Памогите плиз!" Задача вот в чем : телефонный справочник (по фамилии и/или имени и/или отчеству найти номер телефона). Реализовать с помощью Хэш-таблиц. Пролема в том что если вводиш Однофамильцев (например Иванов Сергей Васильвечи, Иванов Петр Васильевич) выкидывает с ошибкой мол имя уже использовано.... Есть в стандартной Hashtable какая нить примочка для записи 2 объектов с одинаковым именем??????Заранее спс
0
Goldywhite
45 / 45 / 3
Регистрация: 18.10.2009
Сообщений: 119
22.11.2009, 14:44 6
Вы можете в хэш таблицу класть массив (или List) из элементов.
C#
1
2
3
4
5
6
7
var entry = hash[str];
if(entry!=null){
(entry as List<?>).Add(value);
}
else {
hash[str] = new List<?>{value};
}
1
Kpactu
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 3
22.11.2009, 15:59 7
а как тогда искать в List?
0
Goldywhite
45 / 45 / 3
Регистрация: 18.10.2009
Сообщений: 119
22.11.2009, 16:10 8
По какому признаку?
1
Kpactu
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 3
22.11.2009, 16:52 9
например записали полей: Иванов Миахила Евгеньич,Петров Василий Иванович,Кондатов Петр Ефрмыч,Иванов Петр Ваильич,Иванов Александор Григорьевич) вВот кароч пишем в фамилии Иванов и мне должно выводить : Михаил Евгеньевич-телефон, Петр Васильевич -телефон, Александр Григорьевич-телефон. Вотьтак , по пронципу списка я задачу решил но требуют хэш0таблицей(((
0
Goldywhite
45 / 45 / 3
Регистрация: 18.10.2009
Сообщений: 119
22.11.2009, 19:03 10
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
    class Program
    {
        class Entry
        {
            public string F;
            public string I;
            public string O;
            public string Phone;
            public override string ToString()
            {
                return string.Format("{0} {1} {2}", F ?? "...", I ?? "...", O ?? "...");
            }
            public override bool Equals(object obj)
            {
                return obj is Entry && Equals(obj as Entry);
            }
            public bool Equals(Entry other)
            {
                return Equals(other.F, F) && Equals(other.I, I) && Equals(other.O, O) && Equals(other.Phone, Phone);
            }
 
            public bool Match(Entry obj)
            {
                return (F == null || F == obj.F) && (I == null || I == obj.I) && (O == null || O == obj.O);
            }
        }
        static Hashtable s_cache;
        static void Add(Entry e)
        {
            Add(e.F, e);
            Add(e.I, e);
            Add(e.O, e);
        }
        static void Add(string field, Entry e)
        {
            var lst = s_cache[field];
            if (lst == null)
            {
                s_cache[field] = new List<Entry> { e };
            }
            else
            {
                ((List<Entry>)lst).Add(e);
            }
        }
 
        static List<Entry> Find(Entry e)
        {
            var lst = s_cache[e.F ?? e.I ?? e.O] as List<Entry>;
            if(lst == null) return null;
            return lst.FindAll(e.Match);
        }
        
        static void Main(string[] args)
        {
            s_cache = new Hashtable();
            var e = new Entry { F = "Иванов", I = "Михаил", O = "Евгеньевич", Phone = "1111111" };
            Add(e);
            e = new Entry { F = "Петров", I = "Василий", O = "Иванович", Phone = "2222222" };
            Add(e);
            e = new Entry { F = "Кондатов", I = "Петр", O = "Ефремович", Phone = "3333333" };
            Add(e);
            e = new Entry { F = "Иванов", I = "Петр", O = "Васильевич", Phone = "4444444" };
            Add(e);
            e = new Entry { F = "Иванов", I = "Александр", O = "Григорьевич", Phone = "5555555" };
            Add(e);
 
            e = new Entry {F = "Иванов"};
            FindAndPrint(e);
            Console.WriteLine();
            e.I = "Петр";
            FindAndPrint(e);
            Console.WriteLine();
            e.I = "Василий";
            FindAndPrint(e);
            Console.WriteLine();
            e = new Entry { O = "Ефремович" };
            FindAndPrint(e);
            Console.ReadLine();
        }
 
        private static void FindAndPrint(Entry entry)
        {
            var res = Find(entry);
            Console.Write("По запросу \"{0}\"", entry);
            
            if (res.Count == 0)
                Console.WriteLine(" ничего не найдено.");
            else
            {
                Console.WriteLine(" найдено {0} записей:",res.Count);
                for (var i = 0; i < res.Count; i++)
                {
                    Console.WriteLine("{0} - {1}", res[i], res[i].Phone);
                }
            }
        }
    }
0
new_in_net
278 / 257 / 32
Регистрация: 11.11.2009
Сообщений: 605
22.11.2009, 23:36 11
Цитата Сообщение от Kpactu Посмотреть сообщение
а как тогда искать в List?
Цитата Сообщение от Goldywhite Посмотреть сообщение
По какому признаку?
Можно последовательно, а можно отсортированным держать и двоичным.
А вообще, если в HashTable можно тоже HashTable хранить уже по именам, а там еще один по отчествам.
Я бы даже сказал храним как вам нужный объект до тех пор как он один, больше одного - храним все в HashTable. Не знаю удалось ли мне объяснить мысль...
0
Goldywhite
45 / 45 / 3
Регистрация: 18.10.2009
Сообщений: 119
22.11.2009, 23:58 12
Цитата Сообщение от new_in_net Посмотреть сообщение
Можно последовательно, а можно отсортированным держать и двоичным.
А вообще, если в HashTable можно тоже HashTable хранить уже по именам, а там еще один по отчествам.
Я бы даже сказал храним как вам нужный объект до тех пор как он один, больше одного - храним все в HashTable. Не знаю удалось ли мне объяснить мысль...
Если бы всё так просто было как ты говоришь )))) Сразу видно ты свою БД не писал

Простой пример: дано отчество. Как ты найдёшь запись?
0
new_in_net
278 / 257 / 32
Регистрация: 11.11.2009
Сообщений: 605
23.11.2009, 00:16 13
Цитата Сообщение от Goldywhite Посмотреть сообщение
Если бы всё так просто было как ты говоришь )))) Сразу видно ты свою БД не писал

Простой пример: дано отчество. Как ты найдёшь запись?
В смысле велосипед не изобретаю? Да, не изобретаю, но пользуюсь придуманным во всю )

Вот то что я имею ввиду в качестве пояснения...

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
    struct Person
    {
        public string Last;
        public string First;
        public string MI;
        public string Phone;
    }
    class MyHashTable
    {
        private Hashtable MyDictionary = new Hashtable();
        private string GetKeyByLevel(int level, Person person)
        {
            return (level == 0) ? person.Last : (level == 1) ? person.First : person.MI;
        }
        private void AddPerson(int level, Person person, Hashtable hTbl)
        {
            string key = GetKeyByLevel(level, person);
            object p = hTbl[key];
            if (p == null)
                hTbl.Add(key, person);
            else if (p is Hashtable)
                AddPerson(++level, person, (Hashtable)p);
            else
            {
                Hashtable newHTbl = new Hashtable();
                hTbl.Add(key, newHTbl);
                level++;
                newHTbl.Add(GetKeyByLevel(level, person), p);
                newHTbl.Add(GetKeyByLevel(level, person), person);
            }
        }
        private string GetPhone(int level, Person person, Hashtable hTbl)
        {
            string key = GetKeyByLevel(level, person);
            object p = hTbl[key];
            if (p == null)
                return null;
            else if (p is Hashtable)
                return GetPhone(++level, person, (Hashtable)p);
            else
                return ((Person)p).Phone;
        }
        public void AddPerson(Person person)
        {
            AddPerson(0, person, MyDictionary);
        }
        public string GetPhone(Person person)
        {
            return GetPhone(0, person, MyDictionary);
        }
    }
Добавлено через 3 минуты
А вообще-то говоря не понятно зачем было затевать эти HashTables. Создай DataTable с 4 полями фамилия-имя-отчество-телефон и заполняй/ищи - все что нужно там есть. Именно, что базы данных придумывать не надо, их надо использовать
0
Goldywhite
45 / 45 / 3
Регистрация: 18.10.2009
Сообщений: 119
23.11.2009, 00:52 14
Дык как ты по отчеству найдёшь телефон? Хэштэйбл видимо задание преподавателя. ДатаТэйбл очень медленная хрень, я не помню есть ли там индексы.
Твой метод это кастомный BTree. Ты взял строку Ф И О и строишь индекс по Ф ФИ ФИО. Соответственно поиск по О, И, ИО у тебя работать не будет.
0
new_in_net
278 / 257 / 32
Регистрация: 11.11.2009
Сообщений: 605
23.11.2009, 01:24 15
Цитата Сообщение от Goldywhite Посмотреть сообщение
Дык как ты по отчеству найдёшь телефон? Хэштэйбл видимо задание преподавателя. ДатаТэйбл очень медленная хрень, я не помню есть ли там индексы.
Твой метод это кастомный BTree. Ты взял строку Ф И О и строишь индекс по Ф ФИ ФИО. Соответственно поиск по О, И, ИО у тебя работать не будет.
Не заметил, что там в любой комбинации требовалось. Я понял что по человеку нужно найти телефон. Так естественно не найдешь.
Насчет медленности DataTable - зависит от кол-ва записей, но я перечитав понял, что Hashtable - это требование препода.

Кстати если в твоем решении использовать Hashtable как у меня, то будет быстрее по любому
0
Goldywhite
45 / 45 / 3
Регистрация: 18.10.2009
Сообщений: 119
23.11.2009, 01:58 16
Почему? Быстрее будет использовать три Hashtable. Одну по фамилии одну по имени одну по отчеству.
0
new_in_net
278 / 257 / 32
Регистрация: 11.11.2009
Сообщений: 605
23.11.2009, 02:17 17
Цитата Сообщение от Goldywhite Посмотреть сообщение
Почему? Быстрее будет использовать три Hashtable. Одну по фамилии одну по имени одну по отчеству.
а более сложные комбинации?
думаю что 3-х уровневое дерево из Hashtables должно быть быстрее чем просто 3 Hashtables и List.
ведь List как не крути - последовательный доступ...
0
Goldywhite
45 / 45 / 3
Регистрация: 18.10.2009
Сообщений: 119
23.11.2009, 02:31 18
Цитата Сообщение от new_in_net Посмотреть сообщение
В смысле велосипед не изобретаю? Да, не изобретаю, но пользуюсь придуманным во всю )
Не пользуйся придуманным
Боюсь, что сделаю для тебя открытие но так будет быстрее :
C#
1
2
3
var fio = "Иванов Иван Иванович";
var hash = new Hashtable();
hash[fio] = "111-11-11";
В крайнем случае можно так:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct Person
        {
            public string F;
            public string I;
            public string O;
 
            public bool Equals(Person other)
            {
                return Equals(other.F, F) && Equals(other.I, I) && Equals(other.O, O);
            }
 
            public override bool Equals(object obj)
            {
                if (ReferenceEquals(null, obj)) return false;
                if (obj.GetType() != typeof (Person)) return false;
                return Equals((Person) obj);
            }
 
            public override int GetHashCode()
            {
                unchecked
                {
                    int result = F.GetHashCode();
                    result = (result*397) ^ I.GetHashCode();
                    result = (result*397) ^ O.GetHashCode();
                    return result;
                }
            }
        }
 
var p = new Person{F="Иванов",I="Иван",O="Иванович};
var hash = new Hashtable();
hash[p] = "111-11-11";
Добавлено через 12 минут
Цитата Сообщение от new_in_net Посмотреть сообщение
а более сложные комбинации?
думаю что 3-х уровневое дерево из Hashtables должно быть быстрее чем просто 3 Hashtables и List.
ведь List как не крути - последовательный доступ...
Тогда так:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var f = new Hashtable();
var i = new Hashtable();
var o = new Hashtable();
 
var fi = new Hashtable();
var fo = new Hashtable();
var io = new Hashtable();
 
var fio = new Hashtable();
 
 
var imya = "Иван";
var otch = "Иванович";
var phone = io[imya+" "+otch];
Но все эти извращения приводят к огромному количеству требуемой памяти. Для большого объема данных (например 10млн записей) лучше использовать SortedDictionary.
0
new_in_net
278 / 257 / 32
Регистрация: 11.11.2009
Сообщений: 605
23.11.2009, 02:36 19
Goldywhite, я говорил это по поводу написания "своей" базы.
Да, не спорю, что для каждой конкретной задачи можно написать собственную, уникальную СУБД, которая будет быстрее чем MS SQL Server, Oracle, MS Access и другие сервера и локальные базы данных. Но на деле вы потратите хренову тучу времени и усилий по написанию, тестированию и поддержке того, что сделано для вас профессионалами, которые предусмотрели даже то, с чем вы еще не столкнулись, с гораздо более высокой надежностью и отказоустойчивостью. А если в результате написания своей базы вы и добьетесь небольшого улучшения скорости по сравнению с известными БД, то поверьте это временно, и с лихвой будет потеряно в других местах позже - либо в скорости, либо по времени разработки.
Это я про велосипед. В общем я за то, чтоб не изобретать велосипед, а его использовать. Пусть изобретают его те, кто соревнуется в выпуске этих велосипедов.
Я - любитель логики и красоты решения, писать базу, которая на милионе записей будет аж на целых 7% быстрее SQL Servera - мне не будет интересно )))))

Но это все лирика. А так... каждый решает для себя как он это хочет делать.
0
Goldywhite
45 / 45 / 3
Регистрация: 18.10.2009
Сообщений: 119
23.11.2009, 03:24 20
60тыс операций поиска в секунду при выборке из 10млн записей. На 64-битной оси требует 6Гб памяти. Поддерживаются любые, как стандартные, так и комплексные типы данных. Поддержка SQL запросов, Представлений. Бинарная сериализация любых структур (быстрее чем BinaryFormatter в 4 раза, и требует только необходимое для самих данных место)... Написано за месяц. 431кб кода. Параллельно пришлось написать универсальный парсер синтаксиса/компилятор/интерпретатор (сейчас поддерживаются SQL и JavaScript). Из мелочей - поддержка транспортного протокола MySQL. Работает под Mono и .NET. Это просто одна из частных задач которую надо было решить Может я и не выбираю простых путей, но покупать то, что работает не достаточно быстро, не привык
Я протестировал с десяток вариантов индексирования как на скорость так и на занимаемый объем памяти. Знаю каждую MSIL инструкцию в реализации классов Hashtable, SortedList и SortedDictionary как в исполнении Microsoft, так и в исполнении Novell Написал сам пару реализаций возможных индексов.

Для решения простых задач всё это не требуется. Для решения критически важных задач приходится разбираться в сути вещей, может и не придётся использовать написанную базу, но за месяц её написания я получил очень много опыта, и это несомненно важно для меня .

Добавлено через 3 минуты
В принципе на форуме зарегистрировался с одной целью - получать опыт. Но пока получается только делиться Тут как-то не хватает споров и дискуссий. Большинство тем: задали задачу, помогите решить
0
23.11.2009, 03:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.11.2009, 03:24

Самый быстрый способ получить хеш строки
Добрый день! Такая проблема. Мне нужно искать дублированные строки в файле...

Алгоритм хеш функции SHA256. Разбор кода
Найден в интернете код алгортима SHA256, помогите разобраться в коде, что...

Реализовать хеш-функцию "One At A Time" Боба Дженкинса
Помогите написать хеш-функцию, её код на C++: unsigned int...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru