VPF::Создание HashMap - Форум программистов

Illusion

Дата 9.6.2006, 23:46 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 9.6.2006

Репутация: нет
Всего: нет

У меня есть задачка такая, про автобусы:
Автобусы (список)
Составить программу, которая содержит динамическую информацию о наличии
автобусов в автобусном парке.
Сведения о каждом автобусе включают:

- номер автобуса;
- фамилию и инициалы водителя;
- номер маршрута;

Программа должна обеспечивать:
- начальное формирование данных обо всех автобусах в парке в виде списка;

- при выезде каждого автобуса из парка вводится номер автобуса, и программа
  удаляет данные об этом автобусе из списка автобусов, находящихся в парке, и
  записывает эти данные в список автобусов, находящихся на маршруте;

- при въезде каждого автобуса в парк вводится номер автобуса, и
  программа удаляет данные об этом автобусе из списка автобусов,
  находящихся на маршруте, и записывает эти данные в список автобусов,
  находящихся в парке;

- по запросу выдаются сведения об автобусах, находящихся в парке, или об
  автобусах, находящихся на маршруте.

Вот... Я написал программку, но в ней используется библиотечный HashMap. А мне нужно без этого, т.е. нужно самому написать подобный класс... Тока вот я понятия не имею, как это сделать. Если кто может, помогите, пожалуйста!

Beard

Дата 9.6.2006, 23:49 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 228
Регистрация: 5.7.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 9

Так взять и посмотреть на исходники стандартного HashMap-а да и реализовать самому
нечто подобное для своей задачи

Illusion

Дата 10.6.2006, 00:04 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 9.6.2006

Репутация: нет
Всего: нет

Это, конечно логично. И я даже пытался. Но ничего толкового не получилось

Beard

Дата 10.6.2006, 00:18 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 228
Регистрация: 5.7.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 9

Так что не получилось?
Давайте уж подробно - в чем сложность в переделке стандартного хэшмепа?

Это сообщение отредактировал(а) Beard - 10.6.2006, 00:19

Illusion

Дата 10.6.2006, 13:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 9.6.2006

Репутация: нет
Всего: нет

Мне, собственно, нужен не весь хэшмап, а только некоторые функции:
put(ключ, значение) - положить в контейнер
get(ключ) - получить значение по ключу
remove(ключ) - удалить значение по ключу
и еще - это конструкция итераторов. Создание самого итератора. Методы values() и iterator(). Ну и для него метод hasnext() - проверка, есть ли еще значения в контейнере и next() - что-то типо get, но вытаскивает просто следующее значение.

LSD

Дата 10.6.2006, 15:36 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 15
Всего: 538

Я когда-то писал подобный класс, для своих нужд. Только итератора в нем нет и нет rehash-а.

Код

public class Hash
{
  public static final int CAPACITY = 1024;

  private Entry[] table;
  private int size;

  public Hash()
  {
    table = new Entry[CAPACITY];
  }

  public int size()
  {
    return size;
  }

  public boolean isEmpty()
  {
    return size == 0;
  }

  public boolean contains(Object key)
  {
    int hash = key.hashCode();
    int i = hash & (table.length - 1);
    Entry entry = table[i];
    while(entry != null)
    {
      if(entry.key.hashCode() == hash && key.equals(entry.key))
        return true;
      entry = entry.next;
    }
    return false;
  }

  public Object get(Object key)
  {
    int hash = key.hashCode();
    int i = hash & (table.length - 1);
    Entry e = table[i];
    while(true)
    {
      if(e == null)
        return e;
      if(e.key.hashCode() == hash && key.equals(e.key))
        return e.value;
      e = e.next;
    }
  }

  public void put(Object key, Object value)
  {
    int hash = key.hashCode();
    int i = hash & (table.length - 1);

    for(Entry e = table[i]; e != null; e = e.next)
    {
      if(e.key.hashCode() == hash && key.equals(e.key))
      {
        e.value = value;
        return;
      }
    }

    table[i] = new Entry(key , value , table[i]);
    size++;
  }

  public void remove(Object key)
  {
    int hash = key.hashCode();
    int i = hash & (table.length - 1);
    Entry prev = table[i];
    Entry entry = prev;

    while(entry != null)
    {
      Entry next = entry.next;
      if(entry.key.hashCode() == hash && key.equals(entry.key))
      {
        size--;
        if(prev == entry)
          table[i] = next;
        else
          prev.next = next;
        return;
      }
      prev = entry;
      entry = next;
    }
  }

  public void clear()
  {
    size = 0;
    for(int i = 0; i < table.length; i++)
      table[i] = null;
  }

  public Object[] keys()
  {
    Object[] keys = new Object[size];
    int j = 0;
    for(int i = 0; i < table.length; i++)
    {
      Entry entry = table[i];
      while(entry != null)
      {
        keys[j++] = entry.key;
        entry = entry.next;
      }
    }
    return keys;
  }

  private int length(Entry entry)
  {
    int i = 0;
    while(entry != null)
    {
      i++;
      entry = entry.next;
    }
    return i;
  }

  private static class Entry
  {
    public Object key;
    public Object value;
    public Entry next;

    public Entry(Object k , Object v , Entry n)
    {
      value = v;
      next = n;
      key = k;
    }

    public Object setValue(Object newValue)
    {
      Object oldValue = value;
      value = newValue;
      return oldValue;
    }

    public boolean equals(Object o)
    {
      if(! (o instanceof Entry))
        return false;
      Entry e = (Entry) o;
      return key.equals(e.key) && (value == e.value || (value != null && value.equals(e.value)));
    }

    public int hashCode()
    {
      return key.hashCode() ^ (value == null ? 0 : value.hashCode());
    }

    public String toString()
    {
      return key + "=" + value;
    }
  }
}

--------------------

Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.

Illusion

Дата 10.6.2006, 17:24 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 9.6.2006

Репутация: нет
Всего: нет

Спасибо за класс. А итератора нет? И почему, когда я смотрю библиотечный класс хэшмэп, там подсвечивается сразу немеренно ошибок?
Вот например метод values()

Код


 public Collection values()
  {
    if (values == null)
      // We don't bother overriding many of the optional methods, as doing so
      // wouldn't provide any significant performance advantage.
      values = new AbstractCollection()
             {
               public int size()
               {
                 return size;
               }

               public Iterator iterator()
               {
                 // Cannot create the iterator directly, because of LinkedHashMap.
                 return Hash.this.iterator(VALUES);
               }

               public void clear()
               {
                 Hash.this.clear();
               }
             };
    return values;
  }

переменная values нигде не определяется, но это не мешает ведь всему работать smile

Beard

Дата 11.6.2006, 06:48 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 228
Регистрация: 5.7.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 9

Цитата(Illusion @ 10.6.2006, 17:24

)

И почему, когда я смотрю библиотечный класс хэшмэп, там подсвечивается сразу немеренно ошибок?

Помню, когда старой Idea пользовался, там проблемы с Javadoc-ом были - тоже кучу ошибок показывала...

Цитата(Illusion @ 10.6.2006, 17:24

)

переменная values нигде не определяется, но это не мешает ведь всему работать

А values опеределены в AbstractMap, который является предком HashMap-а (кстати, а какой JDK вы пользуетесь - 1.4.2 я точно такого кода не видел (про 1.5.0 и не говорю - там бы генерики были)?):

Код


    transient volatile Collection values = null;

А по поводу итератора - можно по аналогу keys() сделать метод values() :

Код


        public Object[] values() {
            Object[] values = new Object[size];
            int j = 0;
            for (int i = 0; i < table.length; i++) {
                Entry entry = table[i];
                while (entry != null) {
                    values[j++] = entry.value;
                    entry = entry.next;
                }
            }
            return values;
        }

а потом:

Код


        public Iterator iterator() {
            return java.util.Arrays.asList(values()).iterator();
        }

Ну а если вообще нельзя пользоваться java.util.*, то что-нить в этом духе:

Код


        public Iterator iterator() {
            return new Iterator() {
                private final Object[] values = values();
                private int count = 0;
                public void remove() {
                    throw new UnsupportedOperationException("not implemented");
                }

                public boolean hasNext() {
                    return count < values.length;
                }

                public Object next() {
                    if (!hasNext())
                        throw new NoSuchElementException();
                    return values[count++];  
                }
            };
        }

Только в таком случае итератор "живет" отдельно от нашего мэпа...
Но можно завести по аналогу стандартного хэшмэпа

Код


    int modCount;

и везде, где происходят изменения в мэпе (get/put...) делать

Код


    modCount++;

а в итераторе смотреть - если у нас отличается modCount от того числа, что было при
инициализации итератора, то бросать ConcurrentModificationException

Illusion

Дата 11.6.2006, 13:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 9.6.2006

Репутация: нет
Всего: нет

Спасибо. Поменял у себя пару вещей и все работает! smile

Вот только modcount? Вроде и без него работает.

LSD

Дата 11.6.2006, 13:46 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 15
Всего: 538

Цитата(Illusion @ 11.6.2006, 14:15

)

Вот только modcount? Вроде и без него работает.

modCount нужен чтобы отслеживать изменения, если например был добавлен элемент, то это может нарушить порядок итерации, и в таком случае просто выбрасывается исключение ConcurrentModificationException. Хотя если у тебя просто учебный пример, то это не нужно.

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java tools & IDE's \| Следующая тема »