在arrayList中使用IndexOf与自定义对象

Question

我希望能够使用indexOf方法返回对象的位置，但只想通过联系人的名称来搜索，有没有办法实现这个功能？

我目前有这个方法：

private static ArrayList<Contacts> contactList = new ArrayList<Contacts>();

public class Contacts {
private String name;
private String number;


public Contacts(String name, String number) {
    this.name = name;
    this.number = number;
}

public String getName() {
    return name;
}

public String getNumber() {
    return number;
}

public void setName(String name) {
    this.name = name;
}

public void setNumber(String number) {
    this.number = number;
}



public int findItem(String name) {

    return contactList.indexOf(name);
}

- PacketSniffer

Answer 1

这里有一个函数可以在不遍历整个列表的情况下实现这一点，我认为复杂度小于O(n)：

public int findItem(String name)
    {
        int max = contactList.size();

        //you might have to subtract this by one 
        //I'm not sure off the top
        int descCnt = max;


        for(int cnt = 0; cnt <= max/2; cnt++)
        {
            if(contactList.get(cnt).getName().equals(name)) return cnt;
            if(contactList.get(descCnt).getName().equals(name)) return descCnt;
            --descCnt;
        }

    }

- Sam Orozco

---

不，它仍然是O(n)。这种“优化”很可能会使事情变得更慢，因为从列表的任一端获取项目可能会导致更多的缓存获取。 - Andy Turner

复杂度为O(n)。你的for循环可能只进行了一半的迭代，但你仍然检查了每个元素。这与逐个迭代整个数组没有什么区别。 - nasukkin

@SamOrozco 如果你有 n 个项目，最坏情况下你不能比检查所有的 n 个更好。如果你可以预处理列表，那么你可以做得更好：如果列表已经排序，你可以在 O(log n) 的时间内完成。如果你可以将项目放入名称到项目的 HashMap 中，你可以在 O(1) 的时间内完成。 - Andy Turner

我不确定你是否能做到。如果 descCnt == contactList.size()，那么 contactList.get(descCnt) 将抛出一个 IndexOutOfBoundsException 异常。请注意，您可以在 for 循环声明中声明并修改 descCnt：for (int cnt = 0, descCnt = max - 1; cnt <= descCnt; cnt++, descCnt--)。 - Andy Turner

@AndyTurner 我觉得你可能会这样做，只是我不确定。我应该去查一下。我不知道在for循环中声明变量的那个特点，这真的很有帮助。谢谢你。 - Sam Orozco

Answer 2

如果你需要根据姓名频繁查找 Contacts，你可以将实例放入一个 Map<String, Contacts> 中。具体使用的 Map 类型取决于你的需求；HashMap 可能就足够了。

代替 contactList.add(contacts)，你可以使用：

contactMap.put(contacts.getName(), contacts);

然后使用以下方法在地图中查找项目：

contactMap.get(someName);

这样做查找会比每次扫描列表更快：对于哈希映射，每次查找都是O(1)，而对于列表则是O(n)。然而，它使用的内存更多。

---

顺便提一下，你的Contacts类看起来像是表示单个联系人，因此应该以单数形式命名为Contact。

此外，你的find方法当前声明为实例方法：

public int findItem(String name) {

这意味着你实际上需要一个 Contacts 实例来查找另一个 Contacts 实例。因此，将其声明为 static：

public static int findItem(String name) {

那么你就可以在没有实例的情况下调用它：

Contacts found = Contacts.find("name");

- Andy Turner

Answer 3

如果您感兴趣，更好的方法是在对象中覆盖equals()和hashcode()方法，并以正确的方式使用indexOf()。

通过基于名称确定相等性，您的equals()方法可以消除所有额外和不必要的代码。

- Olga

Answer 4

你所询问的并不在List#indexOf(Object)的合同中，因此，不，你不应该尝试让列表以那种方式工作。

相反，你可以编写自己的方法，相对容易地实现你想要的功能。只需遍历列表并找到与指定名称匹配的联系人即可。

/**
 * Returns the List index of the Contact with the specified name. If no such
 * Contact is found, -1 will be returned.
 */
public int findItem(String name) {
    for (int i = 0; i < contactList.size(); i++) {
        Contact contact = contactList.get(i);
        if (null == contact) continue;
        if (java.lang.Objects.equals(name, contact.getName())) return i;
    }
    return -1;
}

- nasukkin

---

@SamOrozco 那又怎样？问题中并没有提到性能方面的考虑。即便如此，对于任意ArrayList来说，这种方法已经是最好的了。如果数组按名称排序，我们可以进行一些更高级的搜索，并将复杂度降至O(ln(n))，但同样，问题中也没有提到复杂度要求或可排序性。 - nasukkin

抱歉之前的评论有些混淆了。 - Sam Orozco

Answer 5

补充一下，我已经能够以这种方式完成：

public void searchItem(String name) {
    for(int i = 0; i < contactList.size(); i++) {
        if(name.equals(contactList.get(i).getName())) {
            System.out.println("Found " + name);
            break;
        }
        else {
            System.out.println("Could not find name!");
        }
    }
}

然而，如果我要处理更大的列表，这不是相当低效的吗？有更有效的方法吗？

- PacketSniffer

---

效率低下？你的应用程序遇到了性能问题，需要担心优化你所编写的代码吗？请记住：过早地进行优化是万恶之源。你在这里编写的搜索列表的方式很好。 - nasukkin

contactList 是一个 ArrayList，因此这样做是相当高效的（除了在找到项目之前在每次迭代中打印“找不到名称”）。如果您将其更改为 LinkedList（例如），则效率会降低，因为在链表中列表检索是 O(n)（与像 ArrayList 这样的 RandomAccess 列表中的 O(1) 不同）。 - Andy Turner